C++ easy solution. no sorting. 300ms Beats 100.00%
\n# Code\ncpp []\nclass Solution {\npublic:\n    vector<long long >res;\n    void merge(auto tp, array<long long ,6> &arr){\n        int i=0,j=0;\n        while
\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<long long >res;\n    void merge(auto tp, array<long long ,6> &arr){\n        int i=0,j=0;\n        while(i<6 && j<6){\n            if((arr[i]<tp[j] && i<3) || (i>=3 &&  arr[i]>tp[j])){\n                if(i==0||i==3){\n                    swap(arr[i+1],arr[i+2]);\n                    swap(arr[i],arr[i+1]);\n                } else if(i==1||i==4){\n                    swap(arr[i],arr[i+1]);\n                }\n                arr[i]=tp[j++];\n            }\n            i++;\n            if(i==3)j=3;\n        }\n    }\n    array<long long ,6> dfs(int a,vector<vector<int>>&v,vector<int>&cost,int par){\n        array<long long ,6> arr; //intializing with some dummy value\n        arr[0]=cost[a]>=0?cost[a]:-1e5;arr[1]=-1e5;arr[2]=-1e5;\n        arr[3]=cost[a]<0?cost[a]:1e5;arr[4]=1e5;arr[5]=1e5;\n        for(auto x:v[a]){\n            if(x!=par){\n                auto tp=dfs(x,v,cost,a);\n                int i=0,j=0;\n                merge(tp,arr);//merging in linear time so sorting is not required\n            }\n        }\n        int cnt=6;\n        for(auto x:arr)if(x==1e5 ||x==-1e5)cnt--;\n        if(cnt<3)res[a]=1;\n        else {\n            long long t=0; //for handling dummy value\n            long long a1=max(t,arr[0]),b1=max(t,arr[1]),c1=max(t,arr[2]);\n            long long a2=min(t,arr[3]),b2=min(t,arr[4]),c2=min(t,arr[5]);\n            res[a]=max(a1*b1*c1,a1*a2*b2);\n        }\n        return arr;\n    }\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int i,j,n=cost.size(),m=edges.size();\n        vector<vector<int>>v(n);\n        for(auto x:edges){v[x[0]].push_back(x[1]);v[x[1]].push_back(x[0]);}\n        res=vector<long long >(n,0);\n        dfs(0,v,cost,-1);\n        return res;\n    }\n};\n```
['C++']