C++ | Simple Traversal
Do a basic traversal and keep a track of the max 3 and min 2 cost values for each subtree\n\n\ntypedef long long ll;\n\nstruct SubTreeInfo{\n    int nodeCnt;\n 
Do a basic traversal and keep a track of the max 3 and min 2 cost values for each subtree\n\n```\ntypedef long long ll;\n\nstruct SubTreeInfo{\n    int nodeCnt;\n    vector<ll> val;\n    vector<ll> minVal;\n    \n    SubTreeInfo(){\n        nodeCnt = 1;\n        val.assign({3, INT_MIN});\n    }\n};\n\nclass Solution {\n    vector<ll> res;\npublic:\n    \n    SubTreeInfo populateCoins(vector<vector<int>>& adj, int u, int par, vector<int>& cost){\n        SubTreeInfo treeInfo;\n        vector<ll> valArr(3, INT_MIN);\n        vector<ll> minValArr(2, INT_MAX);\n        for(auto& v : adj[u]){\n            if(v != par){\n                SubTreeInfo currTreeInfo = populateCoins(adj, v, u, cost);\n                treeInfo.nodeCnt += currTreeInfo.nodeCnt;\n                for(auto& val : currTreeInfo.val){\n                    if(val > valArr[0]) valArr[2] = valArr[1], valArr[1] = valArr[0], valArr[0] = val;\n                    else if(val > valArr[1]) valArr[2] = valArr[1], valArr[1] = val;\n                    else if(val > valArr[2]) valArr[2] = val;\n                }\n                \n                for(auto& val : currTreeInfo.minVal){\n                    if(minValArr[0] != INT_MIN && val < minValArr[0]) minValArr[1] = minValArr[0], minValArr[0] = val;\n                    else if(minValArr[0] != INT_MIN && val < minValArr[1]) minValArr[1] = val;\n                }\n            }\n        }\n        \n        int val = cost[u];\n        if(val > valArr[0]) valArr[2] = valArr[1], valArr[1] = valArr[0], valArr[0] = val;\n        else if(val > valArr[1]) valArr[2] = valArr[1], valArr[1] = val;\n        else if(val > valArr[2]) valArr[2] = val;\n        \n        if(minValArr[0] != INT_MIN && val < minValArr[0]) minValArr[1] = minValArr[0], minValArr[0] = val;\n        else if(minValArr[0] != INT_MIN && val < minValArr[1]) minValArr[1] = val;\n        \n        if(treeInfo.nodeCnt < 3){\n            res[u] = 1;\n        }else{\n            ll maxProd = ((ll)valArr[0]*(ll)valArr[1]*(ll)valArr[2]);\n            if(minValArr[0] != INT_MAX && minValArr[1] != INT_MAX){\n                maxProd = max(maxProd, (valArr[0]*minValArr[0]*minValArr[1]));\n            }\n            res[u] = (maxProd < 0 ? 0 : maxProd);\n        }\n        \n        treeInfo.val = valArr;\n        treeInfo.minVal = minValArr;\n        \n        return treeInfo;\n    }\n    \n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n = cost.size();\n        res.resize(n);\n        \n        vector<vector<int>> adj(n);\n        for(auto &edge : edges){\n            int u = edge[0], v = edge[1];\n            adj[u].push_back(v);\n            adj[v].push_back(u);\n        }\n        \n        populateCoins(adj, 0, -1, cost);\n        return res;\n    }\n};\n```
['C']