Python Solution | DFS | Optimized | 1631ms, Beats 93% Time
Approach\n Describe your approach to solving the problem. \nCreate the adjacency list from the edges given. Traverse the adjacency list with DFS. While traversi
# Approach\n<!-- Describe your approach to solving the problem. -->\nCreate the adjacency list from the edges given. Traverse the adjacency list with DFS. While traversing, keep track of the largest three and smallest 2 numbers from its sub trees. As per problem compare the conditions and set the cost value to 1, 0 or max possible product.\n\n\n\n# Code\n```python []\nclass Solution:\n    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n        tree, self.ans = defaultdict(list), [0] * len(cost)\n        # Create the tree\'s adjacency list\n        for startNode, endNode in edges:\n            tree[startNode].append(endNode)\n            tree[endNode].append(startNode)\n        \n        def dfs(curNode: int, prevNode: int):\n            usefulCost = [cost[curNode]]\n            for nextNode in tree[curNode]:\n                if nextNode == prevNode: continue\n                # go deep into the leaf nodes first\n                res = dfs(nextNode, curNode)\n                # accumulate all the cost from all its child node at root level\n                usefulCost.extend(res)\n            # After traversing all sub tree, sort the cost accumulated in reverse order\n            usefulCost.sort(reverse = True)\n            # check if the size of the sub tree less than 3. \n            # If yes, set cost to 1 and return from here.\n            if len(usefulCost) < 3: \n                self.ans[curNode] = 1 \n                return usefulCost\n            # check if the product of the 2nd larget and 3rd larget\n            # is greater than smallest two numbers \n            # as two smaller values are negative and after multiplication \n            # they may give larger values\n            if usefulCost[1] * usefulCost[2] > usefulCost[-1] * usefulCost[-2]:\n                self.ans[curNode] = usefulCost[0] * usefulCost[1] * usefulCost[2];  \n            else:\n                self.ans[curNode] = usefulCost[0] * usefulCost[-1] * usefulCost[-2];   \n            if self.ans[curNode] < 0: self.ans[curNode] = 0\n            if len(usefulCost) <= 5: return usefulCost\n            # return largest 3 and smallest two items, only those can \n            # be useful in later on step and discard others.\n            return usefulCost[0], usefulCost[1], usefulCost[2], usefulCost[-2], usefulCost[-1]\n\n        # Run DFS on the tree and return the answer\n        dfs(0, -1)\n        return self.ans\n```
['Dynamic Programming', 'Tree', 'Depth-First Search', 'Sorting', 'Python', 'Python3']