Python || Optimized Brute Force || DFS
Just maintain at max 3 positive values with max value and 3 negative values with max absolute value as return value of dfs. Now run an O(6 * 5 * 4) brute loop o
Just maintain at max 3 positive values with max value and 3 negative values with max absolute value as return value of dfs. Now run an O(6 * 5 * 4) brute loop on all 6 values and take max. Simple and straightforward.\nTime Complexity - O(n)\nOn paper its 20000 * 6 * 5 * 4 = 2.4 x 10^6 so fast enough to pass :)\n```\nclass Solution:\n    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n        n=len(cost)\n        ans=[1]*n\n        graph=defaultdict(list)\n        for u,v in edges: \n            graph[u].append(v)\n            graph[v].append(u)\n        def dfs(node,par):\n            gg_p,gg_n=[],[]\n            if cost[node]>0: gg_p.append(cost[node])\n            else: gg_n.append(cost[node])\n            for nei in graph[node]:\n                if nei==par: continue\n                gg_pp,gg_nn=dfs(nei,node)\n                gg_p+=gg_pp\n                gg_n+=gg_nn\n            gg_p=sorted(gg_p,reverse=True)[:min(len(gg_p),3)]\n            gg_n=sorted(gg_n)[:min(len(gg_n),3)]\n            nums=[c for c in gg_p+gg_n]\n            m=len(nums)\n            if m>=3:\n                res=0\n                for i in range(m):\n                    for j in range(i+1,m):\n                        for k in range(j+1,m):\n                            res=max(res,nums[i]*nums[j]*nums[k])\n                ans[node]=res\n            return gg_p,gg_n\n        dfs(0,-1)\n        return ans\n```
['Depth-First Search', 'Python']