DFS & track largest 3  & smallest 2 from each sub tree || Very simple and easy to understand
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 2 numbers fr
# 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 2 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\n# Code\n```\n\nvector<long long> ans;\n\nvector<long long> dfs(vector<vector<int>>& t, vector<int>& cost, int root, int par){\n    vector<long long> usefulCost = {cost[root]};\n    for(auto n: t[root]){\n        if(n == par) continue;\n        vector<long long> v = dfs(t, cost, n, root);  //go deep into the leaf nodes first \n        for(auto e: v) usefulCost.push_back(e);  //accumulate all the cost from all its child node at root level\n    }\n\n    // After traversing all sub tree, sort the cost accumulated\n    sort(usefulCost.begin(), usefulCost.end(), greater<long long>());\n    long long sz = usefulCost.size();\n                                                                                        \n    if(usefulCost.size() < 3) { ans[root] = 1; return usefulCost; }  // check if the size of the sub tree less than 3 then set cost to 1 and return from here.\n    if(usefulCost[1] * usefulCost[2] > usefulCost[sz - 1] * usefulCost[sz -2]) {   // check if the product of the 2nd larget and 3rd larget is greater than smallest two numbers ( as two smaller values are negative and after multiplication they may give larger vlaues)\n        ans[root] = usefulCost[0] * usefulCost[1] * usefulCost[2];  \n    }\n    else {\n        ans[root] = usefulCost[0] * usefulCost[sz - 1] * usefulCost[sz - 2];   \n    }\n    if(ans[root] < 0) ans[root] = 0;\n    if(usefulCost.size() <= 5) return usefulCost;\n    return {usefulCost[0], usefulCost[1], usefulCost[2], usefulCost[sz-2], usefulCost[sz-1]};   //return largest 3 and smallest two items, only those can be useful in later on step and discard others.\n}\n\nvector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n    ans.resize(cost.size(), 0); \n    vector<vector<int>> t(cost.size());\n    for(auto e : edges){ t[e[0]].push_back(e[1]); t[e[1]].push_back(e[0]); }\n    dfs(t, cost, 0, -1);\n    return ans;\n}\n```\n\n---\n\n<b>Here is an article of my last interview experience - A Journey to FAANG Company, I recomand you to go through this to know which all resources I have used & how I cracked interview at Amazon:\nhttps://leetcode.com/discuss/interview-experience/3171859/Journey-to-a-FAANG-Company-Amazon-or-SDE2-(L5)-or-Bangalore-or-Oct-2022-Accepted\n\n---
['C++']