Heap DFS - Easy to understand
Intuition\n Describe your first thoughts on how to solve this problem. \nStraighforward DFS problem. When you visit a node, memorize the total number of nodes i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nStraighforward DFS problem. When you visit a node, memorize the total number of nodes in its subtree, its 3 largest cost values and 2 smallest negative cost values (if there\'re any) in its subtree (because the maximum value calculated can only be either product of the 3 largest cost values or product of the 2 minimum negative values with the largest cost value in its subtree)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Create a tree from the given edges\n- Iterate through all children of the current node\n- Foreach node, maintain a minHeap (for 3 maximum cost values) and a maxHeap (for 2 minimum negative cost values).\n- After iterating through all children, calculate the maximum coins placed using the 2 given rules\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 = len(cost)\n        tree = [[] for _ in range(n)]\n        for s, d in edges:\n            tree[s].append(d)\n            tree[d].append(s)\n        result = [0] * n\n        \n        visited = set()\n        def dfs(currentNode):\n            nonlocal result, visited\n            visited.add(currentNode)\n            count = 1\n            heap = [cost[currentNode]]\n            negativeHeap = []\n            if cost[currentNode] < 0: negativeHeap = [-cost[currentNode]]\n            for neighbor in tree[currentNode]:\n                if neighbor not in visited:\n                    subCount, subHeap, subNegHeap = dfs(neighbor)\n                    count += subCount\n                    for e in subHeap:\n                        heappush(heap, e)\n                        if len(heap) > 3: heappop(heap)\n                    for e in subNegHeap:\n                        heappush(negativeHeap, e)\n                        if len(negativeHeap) > 2: heappop(negativeHeap)\n            if count < 3: result[currentNode] = 1\n            else:\n                p = 1\n                for e in heap: p *= e\n                rs = p\n                if len(negativeHeap) == 2:\n                    neg = negativeHeap[0] * negativeHeap[1]\n                    rs = max(rs, neg*max(heap))\n                if rs < 0: result[currentNode] = 0\n                else: result[currentNode] = rs\n            return count, heap, negativeHeap\n        dfs(0)\n        return result\n```
['Depth-First Search', 'Heap (Priority Queue)', 'Python3']