2 DFS || Product of 2 Min and 1 Max or Product of first 3 Max
\nclass Solution {\npublic:\n    vector<int>store;\n    vector<bool>visited;\n    vector<multiset<int>>store1;\n    vector<multiset<int>>store2;\n    vector<lon
```\nclass Solution {\npublic:\n    vector<int>store;\n    vector<bool>visited;\n    vector<multiset<int>>store1;\n    vector<multiset<int>>store2;\n    vector<long long>answer;\n    void dfs(int node, vector<vector<int>>&graph) {\n        \n        visited[node] = true;\n        \n        for(int ne: graph[node]) {\n             if(!visited[ne]) {\n                  dfs(ne, graph);\n                  store[node] += store[ne];\n             }\n        }\n        store[node] +=1;\n    }\n    \n      void dfs1(int node, vector<vector<int>>&graph, vector<int>&cost) {\n        \n        visited[node] = true;\n        \n         for(int ne: graph[node]) {\n              if(!visited[ne]) {\n                  dfs1(ne, graph, cost);\n                  store1[node].insert(store1[ne].begin(), store1[ne].end());\n                  store2[node].insert(store2[ne].begin(), store2[ne].end());\n              }\n         }\n          \n        store1[node].insert(cost[node]);\n        store2[node].insert(cost[node]);\n        auto f = store1[node].begin();\n        auto f2 = prev(store2[node].end());\n         while(store1[node].size() > 3) {\n             store1[node].erase(f++);\n        }\n          while(store2[node].size() > 2) {\n               store2[node].erase(f2--);\n          }\n             \n          \n        if(store[node] >=3) {\n            long long ans1 = numeric_limits<long long>::min(), ans2 = ans1;\n             if(store2[node].size() >=2 and store1[node].size() >=1) {\n                 long long f1 = *store2[node].begin(), f2 = *next(store2[node].begin()), f3 = *prev(store1[node].end());\n                 ans1 = f1*f2*f3;\n             }\n             if(store1[node].size() >=3) {\n                  int counter = 0;\n                 long long t = 1;\n                 auto f = prev(store1[node].end());\n                 while(counter < 3) {\n                      counter++;\n                      t*=(*f);\n                      f--;\n                 }\n                 ans2 = t;\n             }\n            \n             ans1 = max(ans1, ans2);\n            if(ans1 < 0)answer[node] = 0;\n            else answer[node] = ans1;\n        }else answer[node] = 1;\n        \n    }\n    \n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        vector<vector<int>>graph(cost.size());\n        store.resize(cost.size(),0);\n        visited.resize(cost.size(),false);\n        store1.resize(cost.size());\n          store2.resize(cost.size());\n        for(auto&edge: edges) {\n             graph[edge[0]].push_back(edge[1]);\n             graph[edge[1]].push_back(edge[0]);\n        }\n        \n        answer.resize(cost.size());\n        dfs(0, graph);\n        \n        visited.clear();\n        visited.resize(cost.size(), false);\n        dfs1(0, graph, cost);\n    \n        return answer;\n        \n    }\n};\n```
['Depth-First Search']