Very easy DFS | C++
\n\n# Approach\n- Create the tree from the edges given\n- Traverse to the tree with DFS.\n- While traversing keep track of the largest three and smallest 3 numb
\n\n# Approach\n- Create the tree from the edges given\n- Traverse to the tree with DFS.\n- While traversing keep track of the largest three and smallest 3 numbers from its sub trees.\n- As per problem compare the conditions and set the cost value to 1, 0 or max possible product.\n\n# Code\n```\n#define ll long long\nclass Solution {\npublic:\n    void dfs(ll node, vector<vector<ll>> &adj, ll par, vector<multiset<ll>> &store, vector<multiset<ll>> &store1, vector<int> &cost){\n        for(auto it : adj[node]){\n            if(it != par){\n                dfs(it, adj, node, store, store1, cost);\n                for(auto x : store[it]){\n                    store[node].insert(x);\n                }\n                for(auto x : store1[it]){\n                    store1[node].insert(x);\n                }\n            }\n        }\n        if(cost[node] >= 0) store[node].insert(cost[node]);\n        else store1[node].insert(-cost[node]);\n        while(store[node].size() > 3){\n            store[node].erase(store[node].begin());\n        }\n        while(store1[node].size() > 3){\n            store1[node].erase(store1[node].begin());\n        }\n    }\n\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        ll n = cost.size();\n        vector<vector<ll>> adj(n);\n\n        for (int i = 0; i < n-1; ++i)\n        {\n            ll a = edges[i][0], b = edges[i][1];\n            adj[a].push_back(b);\n            adj[b].push_back(a);\n        }\n\n        vector<multiset<ll>> store(n);\n        vector<multiset<ll>> store1(n);\n\n        dfs(0, adj, -1, store, store1, cost);\n        vector<ll> ans(n, 1);\n\n        for (int i = 0; i < n; ++i)\n        {\n            if(store[i].size() + store1[i].size() >= 3){\n                vector<ll> x;\n                for(auto it : store[i]) x.push_back(it);\n                for(auto it : store1[i]) x.push_back(-it);\n                sort(x.begin(), x.end());\n                ll siz = x.size();\n                ll a = x[siz-1] * x[siz-2] * x[siz-3] , b = x[0] * x[1] * x[siz-1];\n                if(max(a, b) < 0) ans[i] = 0;\n                else ans[i] = max(a, b);\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']