Easy recursion sol || 100% beats || Fastest
Intuition\n Describe your first thoughts on how to solve this problem. \nIf there are are n nodes in a subtree then to maximize the coin for that node we have 2
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf there are are n nodes in a subtree then to maximize the coin for that node we have 2 options\n1. 3 largest elements\n2. largest element and 2 smallest elements ( if these two number are negative then their multiplication will be positive)\n3. So for each node we need to track of 5 elements ( 3 largest and 2 smallest)\n4. From all children get these elements and find the best one for thecurrent node then calculate.\n\n\n# Complexity\n- Time complexity: $$O(n)$$ : Each node will be visited single time.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<long long> ans;\n    vector<long> solve(int node,vector<vector<int>>& child, int par,  vector<int>& cost){\n        vector<long> temp,temp2;\n        for(auto c:child[node]){\n            if(c!=par){\n                temp = solve(c, child, node, cost);\n                for(auto x:temp){\n                    temp2.push_back(x);\n                }\n            }\n        }\n        temp2.push_back(cost[node]);\n        sort(temp2.begin(), temp2.end());\n        if(temp2.size()<3){\n            //if enough nodes  are not present in currents subtree\n            ans[node] = 1;\n            return temp2;\n        }\n        int n = temp2.size();\n        long z = 0;\n        //case 1 : 3 largset\n        long op1 = (long)temp2[n - 1] * (long)temp2[n - 2] * (long)temp2[n - 3];\n        //case 2 : Largset and 2 smallest\n        long op2 = (long)temp2[n - 1] * (long)temp2[0] * (long)temp2[1];\n        ans[node] = max(z, max(op1,op2));  // if negative then make it 0\n        if(temp2.size()<=5){\n            return temp2;\n        }\n        else{\n            return {temp2[n - 1], temp2[n - 2], temp2[n - 3], temp2[0], temp2[1]};\n        }\n    }\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n = cost.size();\n        vector<vector<int>> child(n);\n        for (auto e:edges){\n            child[e[0]].push_back(e[1]);\n            child[e[1]].push_back(e[0]);\n        }\n        ans.resize(n);\n        solve(0, child, -1, cost);\n        return ans; \n    }\n};\n```
['Array', 'Tree', 'Recursion', 'Sorting', 'C++']