O(NlogN) solution using small to large merging 
Return values will be  optimized using RVO.Code
Return values will be  optimized using RVO.


# Code
```cpp []
class Solution {
public:
    using ll=long long;
    vector<vector<int>> g;
    vector<int> sz;
    vector<ll> res;
    int fillsize(int node,int par){
        int ans=1;
        for(auto & child:g[node]){
            if(child!=par){
                ans+=fillsize(child,node);
            }
        }
        return sz[node]=ans;
        
    }
    multiset<ll> dfs(int node,int par,vector<int> & cost){
        multiset<ll> ms1;
        ms1.insert(cost[node]);
        for(auto & child:g[node]){
            if(child!=par){
                multiset<ll> ms2=dfs(child,node,cost);
                if(ms2.size()>ms1.size()){
                    swap(ms1,ms2);
                }
                for(auto & it:ms2){
                    ms1.insert(it);
                }
            }
        }
        if(sz[node]<3){
            res[node]=1;
        }
        else{
            auto it=prev(ms1.end());
            ll cur1=1LL*(*it)*(*(--it))*(*(--it));
            it=ms1.begin();
            ll cur2=1LL*(*it)*(*(++it))*(*ms1.rbegin());
            res[node]=max(cur1,cur2)<0?0:max(cur1,cur2);

        }
        return ms1;
    }
    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {
        g.resize(cost.size());
        for(auto & e:edges){
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        sz.assign(cost.size(),0);
        res.assign(cost.size(),0);
        fillsize(0,-1);
        dfs(0,-1,cost);
        return res;


    }
};
```
['Depth-First Search', 'C++']