Python DFS - Simple
Approach\n Describe your approach to solving the problem. \nDFS pass to track bottom-2 and top-3 subtree costs. Not most memory-efficient, but easy to follow.\n
# Approach\n<!-- Describe your approach to solving the problem. -->\nDFS pass to track bottom-2 and top-3 subtree costs. Not most memory-efficient, but easy to follow.\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n        \n        def dfs(\n            curr_node: int,\n            adj_list: Dict[int, List[int]],\n            cost: List[int],\n            bot2: Dict[int, List[int]],\n            top3: Dict[int, List[int]],\n            coin: list,\n        ):\n            bot2[curr_node] = [cost[curr_node]]\n            top3[curr_node] = [cost[curr_node]]\n\n            for adj_node in adj_list[curr_node]:\n                if adj_node not in bot2:  # if unvisited (and implies child node)\n                    dfs(adj_node, adj_list, cost, bot2, top3, coin)\n                    bot2[curr_node].extend(bot2[adj_node])\n                    top3[curr_node].extend(top3[adj_node])\n\n            if len(top3[curr_node]) < 3:\n                coin[curr_node] = 1\n\n            else:\n                bot2[curr_node] = sorted(bot2[curr_node])[:2]\n                top3[curr_node] = sorted(top3[curr_node])[-3:]\n                coin[curr_node] = max(\n                    (\n                        0,\n                        math.prod(bot2[curr_node]) * top3[curr_node][-1],\n                        math.prod(top3[curr_node]),\n                    )\n            )\n\n            return coin\n\n        # make adjacency-list graph\n        adjList = [[] for _ in range(len(cost))]\n        for u, v in edges:\n            adjList[u].append(v)\n            adjList[v].append(u)\n\n        # compute coin in dfs pass\n        return dfs(0, adjList, cost, bot2={}, top3={}, coin=[0]*len(cost))\n\n```
['Python3']