C++ solution | DFS
The thing to observe here is that the maximum product can either be made from multiplying the 3 largest numbers or from multiplying the largest numbers with the
The thing to observe here is that the maximum product can either be made from multiplying the 3 largest numbers or from multiplying the largest numbers with the 2 smallest numbers (in case of negatice numbers).\nSo at a point we need the 3 largest and the 2 smallest numbers of a node\'s subtree.\n```\nclass Solution {\npublic:\n    vector<priority_queue<long long>> pq;\n    vector<priority_queue<long long, vector<long long>, greater<long long> > >pq2;\n    vector<vector<long long>> adj;\n    void dfs(int node, int par, int n,vector<long long>&ans,vector<int>&cost){\n        for(int i=0;i<adj[node].size();i++){\n            if(adj[node][i]!=par){\n                dfs(adj[node][i],node,n,ans,cost);\n            }\n        }\n        pq[node].push((long long)cost[node]);\n        pq2[node].push((long long)cost[node]);\n        if(pq[node].size()<3){\n            ans[node]=1;\n        }\n        else{\n            long long cur=1,cur2=1;\n            cur*=pq[node].top();\n            cur2=cur;//cur2=highest cost in subtree\n            if(node!=0)pq[par].push(pq[node].top());\n            pq[node].pop();\n            cur*=pq[node].top();\n            if(node!=0)pq[par].push(pq[node].top());\n            pq[node].pop();\n            cur*=pq[node].top();\n            if(node!=0)pq[par].push(pq[node].top());\n            ans[node]=max(cur,0LL);\n            //multiplying smallest two numbers with the largest\n            cur2*=pq2[node].top();\n            if(node!=0)pq2[par].push(pq2[node].top());\n            pq2[node].pop();\n            cur2*=pq2[node].top();\n            if(node!=0)pq2[par].push(pq2[node].top());\n            ans[node]=max(ans[node],cur2);\n            return;\n        }\n        long long sze=pq[node].size(),sze2=pq2[node].size();\n        if(node==0)return;\n        for(int i=0;i<min(sze,3LL);i++){\n            pq[par].push(pq[node].top());\n            pq[node].pop();\n        }\n        for(int i=0;i<min(sze,2LL);i++){\n            pq2[par].push(pq2[node].top());\n            pq2[node].pop();\n        }\n    }\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n=edges.size()+1;\n        pq.resize(n);\n        adj.resize(n);\n        pq2.resize(n);\n        for(int i=0;i<edges.size();i++){\n            int a=edges[i][0],b=edges[i][1];\n            adj[a].push_back(b);\n            adj[b].push_back(a);\n        }\n        vector<long long> ans(n);\n        dfs(0,-1,n,ans,cost);\n        return ans;\n    }\n};\n```\nPlease UPVOTE if you liked the solution!!!
['Depth-First Search', 'Heap (Priority Queue)', 'C++']