O(N) solution
Intuition\nWe first build a map of all the paths,\nfor each node, we keep track of the largest 3 cost inside the subtree, and the smallest 3 cost inside the sub
# Intuition\nWe first build a map of all the paths,\nfor each node, we keep track of the largest 3 cost inside the subtree, and the smallest 3 cost inside the subtree\n\n# Approach\nwe build the tree\nwe dfs (post order traversal) the tree\ndo the calculations on what the answer should be\nwe add the all cost to the parent\'s cost and only keep the largest 3 and smallest 3\n\n# Complexity\n- Time complexity:\nO(N) since sorting 6 items at the calculation level is O(1) and all the heaps have a max of 3 items, so those are also O(1) actions each\n\n\n- Space complexity:\nO(N * V) since heaps have a max size, and we just need to store the vertices and the nodes\n# Code\n```\nfrom collections import defaultdict\nimport heapq\nclass Solution:\n    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n        \n        memo = defaultdict(set)\n        for a,b in edges:\n            memo[a].add(b)\n            memo[b].add(a)\n\n        leaves = [i for i in memo if len(memo[i]) == 1]\n        ans = [1] * len(cost) \n\n        leaf_memo = []\n\n        for i in range(len(cost)):\n            if cost[i] > 0:\n                leaf_memo.append(([cost[i]],[]))\n            else:\n                leaf_memo.append(([],[-cost[i]]))\n\n        @cache\n        def dfs(leaf, parent):\n            for kid in memo[leaf]:\n                if kid != parent:\n                    dfs(kid, leaf)\n\n            if len(leaf_memo[leaf][0]) + len(leaf_memo[leaf][1]) >= 3:\n                A = sorted(leaf_memo[leaf][0] + [-i for i in leaf_memo[leaf][1]])\n                ans[leaf] = max(0, max(A[0] * A[1] * A[len(A) - 1], A[len(A) - 1] * A[len(A) - 2] * A[len(A) - 3]))\n\n            if leaf == 0:\n                return\n\n            while leaf_memo[leaf][0]:\n                heapq.heappush(leaf_memo[parent][0], heapq.heappop(leaf_memo[leaf][0]))\n                if len(leaf_memo[parent][0]) > 3:\n                    heapq.heappop(leaf_memo[parent][0])\n            while leaf_memo[leaf][1]:\n                heapq.heappush(leaf_memo[parent][1], heapq.heappop(leaf_memo[leaf][1]))\n                if len(leaf_memo[parent][1]) > 3:\n                    heapq.heappop(leaf_memo[parent][1])\n\n        dfs(0,0)\n        return ans\n                \n\n\n```
['Python3']