c++, O(n)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\n    vector<int>cost;\n    vector<int>g[20005];\n    int sz[20005];\n    long long ans[20005];\npublic:\n    vector<int>merg(vector<int>v1,vector<int>v2){\n        vector<int>ret;\n        for(auto x:v1) ret.push_back(x);\n        for(auto x:v2) ret.push_back(x);\n        sort(ret.begin(),ret.end());\n        vector<int>retReal;\n        while(ret.size()){\n            retReal.push_back(ret.back()); ret.pop_back();\n            if(retReal.size()>2) break;\n        }\n        return retReal;\n    }\n    pair<vector<int>,vector<int> > go(int u, int p){\n        vector<int>pos,neg;\n        if(cost[u]>=0){\n            pos.push_back(cost[u]);\n        }\n        else{\n            neg.push_back(-cost[u]);\n        }\n        sz[u] = 1;\n        for(auto x:g[u]){\n            if(x == p) continue;\n            pair<vector<int>,vector<int> > res = go(x,u);\n            sz[u]+=sz[x];\n            pos = merg(pos,res.first);\n            neg = merg(neg,res.second);\n        }\n        if(sz[u] < 3){\n            ans[u] = 1;\n        }\n        else{\n            long long cur = 0;\n            if(pos.size()>=3){\n                cur = 1LL*pos[0]*pos[1]*pos[2];\n            }\n            if(pos.size()>0){\n                if(neg.size()>1){\n                    cur = max(cur,1LL*pos[0]*neg[0]*neg[1]);\n                }\n            }\n            ans[u] = cur;\n        }\n        return {pos,neg};\n    }\n    vector<long long> placedCoins(vector<vector<int>>& e, vector<int>& cost) {\n        this->cost = cost;\n        int n = cost.size();\n        for(int i = 0;i<n-1;i++){\n            g[e[i][0]].push_back(e[i][1]);\n            g[e[i][1]].push_back(e[i][0]);\n        }\n        pair<vector<int>,vector<int> > ret = go(0,-1);\n        vector<long long>ansReal;\n        for(int i = 0;i<n;i++) ansReal.push_back(ans[i]);\n        return ansReal;\n    }\n};\n```
['C++']