DFS
Intuition\nThe most critical part to observe is that, You need to have 5 values at each node and not 3.\nThis is because let\'s say if the subtree of the curren
# Intuition\nThe most critical part to observe is that, You need to have $$5$$ values at each node and not $$3$$.\nThis is because let\'s say if the subtree of the current node contains $$5$$ child nodes. Let\'s say there are two negative values and 3 positive values. It may happen that the product of two smallest negative values and the highest positive value is greater than the product of the three highest positive values as -ve * -ve is +ve.\n\nSo, for each node keep $$5$$ values,the $$firstminimum, secondminimum, firstmaximum, secondmaximum, thirdmaximum$$. Now compare the products of $$firstmaximum*secondmaximum*thirdmaximum$$ with $$firstmaximum*secondminimum*firstminimum$$ and whichever is larger store that.\n\n# Complexity\n- Time complexity: $$O(5*n)$$\n- Space complexity: $$O(n)$$, Recursive stack space.\n\n# Code\n```\nclass Solution {\npublic:\n    #define ll long long\n    vector<ll>ans;\n    void updateVal(ll &fmax,ll &smax,ll &tmax,ll &smin,ll &fmin,ll val){\n        if(val > fmax) tmax = smax,smax=fmax,fmax=val;\n        else if(val > smax) tmax = smax,smax = val;\n        else if(val > tmax) tmax = val;\n\n        if(val < fmin) smin = fmin,fmin = val;\n        else if(val < smin) smin = val;\n    }\n\n    vector<ll> dfs(int node,vector<ll> adj[],int par,vector<int>&cost){\n        ll fmax=INT_MIN,smax=INT_MIN,tmax=INT_MIN,fmin=INT_MAX,smin=INT_MAX;\n        vector<ll>cur;\n        int cnt = 1;\n        for(auto ch:adj[node]){\n            if(ch != par){\n                vector<ll>child = dfs(ch,adj,node,cost);\n                for(int i=0;i<child.size();++i){\n                    cnt++;\n                    updateVal(fmax,smax,tmax,smin,fmin,child[i]);\n                }\n            }\n        }\n\n        updateVal(fmax,smax,tmax,smin,fmin,cost[node]);\n        if(cnt < 3){\n            ans[node] = 1;\n            if(cnt == 1) return {fmax};\n            else if(cnt == 2) return {fmax,smax};\n        }else{\n            ans[node] = max({0ll,fmax*smax*tmax,fmax*smin*fmin});\n            cur.push_back(fmin),cur.push_back(smin);\n            if(cnt >= 5) cur.push_back(tmax);\n            if(cnt >= 4) cur.push_back(smax);\n            cur.push_back(fmax);\n        }\n        return cur;\n    }\n\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n=cost.size();\n        ans = vector<ll>(n);\n        vector<ll>adj[n];\n        for(int i=0;i<n-1;++i){\n            int u=edges[i][0],v=edges[i][1];\n            adj[u].push_back(v);\n            adj[v].push_back(u);\n        }\n        dfs(0,adj,-1,cost);\n        return ans;\n    }\n};\n```
['Depth-First Search', 'C++']