An Easy-to-Understand Python3 Solution Using Two Heaps
Intuition\n\nDFS + straightforward dynamical programming + two heaps\n\n# Approach\n\nApply DFS to solve this problem. \n The main observation is that at each n
# Intuition\n\nDFS + straightforward dynamical programming + two heaps\n\n# Approach\n\nApply DFS to solve this problem. \n* The main observation is that at each node, we can obtain a min-heap and a max-heap to store the smallest 3 values and the largest 3 values of this subtree. \n* At a node `n`, we need to go through all children/subtree $(\\mathcal{T}_i)_{i=1, \\ldots, m_n}$ of this parent node and update the min-heap using the $(m_n)$ min-heaps from its subtree and similarly for its max-heap. \n* Note that the list of edges given is undirected, i.e., for $[a_i, b_i]$ it could be possible that $a_i$ is the parent and $b_i$ is the child and the other way around. \n* For memory consideration, we use the list storing coin numbers to indicate whether or not a node is visited or not. \n\n\n# Complexity\n- Time complexity: $\\mathcal{O}(n)$\n    - Each node is visitied only once; the operations to append elements to min/max-heaps and pop out the larger/smaller values only happen when there is an edge. \n\n- Space complexity: $\\mathcal{O}(n)$\n\n# Code\n```\nimport heapq\n\nclass Solution:\n    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n        \n        # Prepare the neighboring dictionary for latter DFS\n        cnt_node = len(cost)\n        ngbh_dict = {x: [] for x in range(cnt_node)}\n        for edge in edges:\n            ngbh_dict[edge[0]].append(edge[1])\n            ngbh_dict[edge[1]].append(edge[0])\n        \n        # Prepare a list to store results; when value = -1, it indicates that the node hasn\'t been visited\n        ans = [-1] * cnt_node\n\n        def dfs(node): \n            ans[node] = 1 # Meant to indicate that this node has been visited\n            l_heap, s_heap = [cost[node]], [-cost[node]]\n            \n            for ngbh in ngbh_dict[node]:\n                if ans[ngbh] != -1:\n                    continue # Avoid visiting parent node\n\n                ch_l_heap, ch_s_heap = dfs(ngbh)\n\n                # Append the min-heap and max-heap of subtree to the current min/max-heaps\n                for val in ch_l_heap:\n                    heapq.heappush(l_heap, val)\n                    if len(l_heap) > 3:\n                        heapq.heappop(l_heap)\n                for val in ch_s_heap:\n                    heapq.heappush(s_heap, -val)\n                    if len(s_heap) > 3:\n                        heapq.heappop(s_heap)\n\n            # Compute the coin number for the current node\n            l_heap = sorted(l_heap, reverse=True)\n            s_heap = sorted([-x for x in s_heap])\n            if len(l_heap) < 3: \n                ans[node] = 1\n            else:\n                coin = max(s_heap[0] * s_heap[1] * l_heap[0], l_heap[0] * l_heap[1] * l_heap[2])\n                if coin < 0: \n                    ans[node] = 0\n                else:\n                    ans[node] = coin\n\n            return l_heap, s_heap\n\n        dfs(0)\n        return ans\n```
['Python3']