easy DFS with brute-sorting
Code\n\nclass Solution:\n    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n\n        g = defaultdict(set) # represents the graph
# Code\n```\nclass Solution:\n    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n\n        g = defaultdict(set) # represents the graph\n        for a, b in edges: # build graph\n            g[a].add(b)\n            g[b].add(a)\n\n        n = len(cost)\n        coin = [1] * n # init the answer\n        \n        def dfs(par, cur): # param: parent id, current id\n            a = [cost[cur]] # the cost array include current and decendents\n            cnt = 1 # subtree nodes count (include current node)\n\n            children = g[cur] - {par} # remove parent node (avoid search back)\n            for nxt in children: # iterate children and update `a` and `cnt`\n                a_, cnt_ = dfs(cur, nxt)\n                a.extend(a_)\n                cnt += cnt_\n            \n            a.sort() # sort the array\n            if cnt >= 3: # update answer if subtree nods count >= 3\n                # if a[0] and a[1] both negative, might have the product greater than a[-3] and a[-2]\n                # so compare the product between (a[0] * a[1] and a[-3] * a[-2])\n                # and according to the description, if final result is negative, we have to make it 0\n                coin[cur] = max(0, a[-1] * max(a[0] * a[1], a[-3] * a[-2]))\n            \n            return a, cnt\n\n        dfs(-1, 0)\n        return coin\n```
['Depth-First Search', 'Sorting', 'Python', 'Python3']