Python3 | DFS | Sorted Containers | Greedy approach
Intuition\n Describe your first thoughts on how to solve this problem. \nThe first thought after reading the question, the nodes traversal is gonna be either DF
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe first thought after reading the question, the nodes traversal is gonna be either DFS or BFS. Since we need number of subtree(s) at every nodes, So let\'s approach this problem with DFS traversal.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBuild an adjacency list (Graph) for unpacking the nodes.\nStart traversing with the current node and search its neighbour\'s nodes, starting with node 0 (since it\'s root node).\nAlso, keep track of visited nodes.\n\nWhenever, we reach at the last node of the current subtree, we need to calculate its length for the sake of updating our ans.\n\nif the length of the current subtree would be less than 3, then we simply put current index value as one, otherwise we will greedily calculate maximum product of 3 numbers in a sorted array as following : \n            i) first_choice = subtree_nodes_cost[0] * subtree_nodes_cost[1] * subtree_nodes_cost[-1] \n            ii) second_choice = subtree_nodes_cost[-1] * subtree_nodes_cost[-2] * subtree_nodes_cost[-3]\n            iii) third_choice = 0 (case when we only get negative numbers in the sorted array)\nIn this way, we calculate maximum product of 3 numbers for current subtree.\n\nI have used SortedList Container so that we could easily get the maximum three nodes and greedily calculated their maximum product.\n\nFinally return the current subtrees nodes (at most 5) to its parent.\n\n# Complexity\n- Time complexity: O(n * log(n)), where n is the number of nodes.\n(here, sorted-containers\' every method works in log(k) time, where k is the number of items.)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n) - (for graph construction and keeping track of visited cells)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfrom collections import defaultdict\nfrom sortedcontainers import SortedList\n\n\nclass Solution:\n    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n        graph = self.build_graph(edges)\n        visited_nodes = set()\n        n = len(cost)\n        ans = [0] * n\n\n        self.distribute_coins(0, graph, visited_nodes, cost, ans)\n\n        return ans\n\n\n    def distribute_coins(self, curr_node, graph, visited_nodes, cost, ans):\n        visited_nodes.add(curr_node)\n\n        # Use sortedList for ease of getting node\'s coin cost in sorted order\n        subtree_nodes_cost = SortedList([cost[curr_node]])\n\n        for neighbour_node in graph[curr_node]:\n            if neighbour_node not in visited_nodes:\n                # Here, we are updating the current parent with its descendants.\n                subtree_nodes_cost.update(self.distribute_coins(neighbour_node, graph, visited_nodes, cost, ans))\n\n        if len(subtree_nodes_cost) < 3:\n            ans[curr_node] = 1\n\n        else:\n            first_choice = subtree_nodes_cost[0] * subtree_nodes_cost[1] * subtree_nodes_cost[-1]\n            second_choice = subtree_nodes_cost[-1] * subtree_nodes_cost[-2] * subtree_nodes_cost[-3]\n            # if both first and second choice would be negative, then keep the maximum product as 0, as the condition states.\n            max_product = max(first_choice, second_choice, 0)\n            ans[curr_node] = max_product\n\n        # We need to have at most six values at each subtree. \n        # We are returning greadily at most 5 subtree\'s nodes from here,\n        # and it will get appended with its parent making 6 subtree\'s nodes.\n        return subtree_nodes_cost if len(subtree_nodes_cost) < 6 else subtree_nodes_cost[0 : 2] + subtree_nodes_cost[-3 : ]\n\n\n    def build_graph(self, edges):\n        graph = defaultdict(list)\n\n        for e1, e2 in edges:\n            graph[e1].append(e2)\n            graph[e2].append(e1)\n\n        return graph\n\n\n\n        \n```
['Greedy', 'Graph', 'Python3']