dfs
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    typedef long long ll;\n    vector<pair<vector<ll>,vector<ll>>> v; //maxi,mini\n    vector<vector<int>> adj;\n    vector<ll> ans;\n    void dfs(int node,int pre,vector<int>& c){\n        v[node].first[0]=c[node];\n        v[node].second[0]=c[node];\n        for(auto i:adj[node]){\n            if(i==pre)continue;\n            dfs(i,node,c);\n            vector<ll> temp=v[i].first;\n            for(int j=0;j<3;j++)temp.push_back(v[node].first[j]);\n            sort(rbegin(temp),rend(temp));\n            for(int j=0;j<3;j++)v[node].first[j]=temp[j];\n            \n            temp=v[i].second;\n            for(int j=0;j<3;j++)temp.push_back(v[node].second[j]);\n            sort(begin(temp),end(temp));\n            for(int j=0;j<3;j++)v[node].second[j]=temp[j];\n\n        }\n        if(v[node].first[2]==-1e5){\n            ans[node]=1;\n            return;\n        }\n        ll maxi=1;\n        for(int j=0;j<3;j++)maxi*=v[node].first[j];\n        ll maxi2=v[node].first[0];\n       \n        maxi2*=v[node].second[0]*v[node].second[1];\n        maxi=max(maxi,maxi2);\n        ans[node]=max(0ll,maxi);\n        \n    }\npublic:\n    vector<long long> placedCoins(vector<vector<int>>& e, vector<int>& c) {\n        int n=c.size();\n        adj.resize(n);\n        v.resize(n);\n        ans.resize(n);\n        ll a=-1e5,b=1e5;\n        for(int i=0;i<n;i++){\n            v[i]={{a,a,a},{b,b,b}};\n        }\n        for(auto i:e){\n            adj[i[0]].push_back(i[1]);\n            adj[i[1]].push_back(i[0]);\n        }\n        dfs(0,-1,c);\n        return ans;\n    }\n};\n```
['C++']