DFS + Sort
As we do DFS, we maintain a list of:\n- up to 2 smallest negative costs\n- up to 3 largest positive costs.\n\nAs we collect costs from children, we sort the com
As we do DFS, we maintain a list of:\n- up to 2 smallest negative costs\n- up to 3 largest positive costs.\n\nAs we collect costs from children, we sort the combined list and discard costs in the middle.\n\n**Python 3**\n```python\nclass Solution:\n    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n        res, al = [0] * len(cost), [[] for _ in range(len(cost))]\n        for  a, b in edges:\n                al[a].append(b)\n                al[b].append(a)\n        def dfs(i: int, p : int) -> List[int]:\n            c = [cost[i]]\n            for j in al[i]:\n                if j != p:\n                    c.extend(dfs(j, i))\n            c.sort()\n            res[i] = 1 if len(c) < 3 else max(0, c[0] * c[1] * c[-1], c[-3] * c[-2] * c[-1])\n            return c if len(c) < 5 else [c[0], c[1], c[-3], c[-2], c[-1]]\n        dfs(0, 0)\n        return res \n```
['Python']