EASY C++ SOLUTION || GRAPH TRAVERSAL || DFS
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
    
    vector<vector<long long>>per_cost;
    void dfs(vector<int>adj[], int node, int par, vector<int>&cost)
    {
        per_cost[node].push_back(cost[node]);
        for(auto &x: adj[node])
        {
            if(x == par)
            continue;
            else
            {
                
                dfs(adj, x, node, cost);
                int m = per_cost[x].size();
                sort(per_cost[x].begin(), per_cost[x].end());
                if(m <= 5)
                {
                    for(auto y: per_cost[x])
                    {
                        per_cost[node].push_back(y);
                    }
                }
                else
                {
                    per_cost[node].push_back(per_cost[x][m-1]);
                    per_cost[node].push_back(per_cost[x][m-2]);
                    per_cost[node].push_back(per_cost[x][m-3]);
                    per_cost[node].push_back(per_cost[x][0]);
                    per_cost[node].push_back(per_cost[x][1]);
                }
            }
        }

    }
public:
    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {
        int n = edges.size();
        vector<int>adj[n+1];
        for(auto x: edges)
        {
            adj[x[0]].push_back(x[1]);
            adj[x[1]].push_back(x[0]);
        }

        per_cost.resize(n+1);

        vector<long long>answer(n+1, 0);

        dfs(adj, 0, -1, cost);

        for(int i=0; i<=n; i++)
        {
            
            vector<long long>&curr = per_cost[i];

            sort(curr.begin(), curr.end());

            int m = curr.size();

            if(m < 3)
            {
                answer[i] = 1;
            }
            else
            {
                
                long long prod1 = curr[m-1]*curr[m-2]*curr[m-3];
                long long prod2 = curr[0]*curr[1]*curr[m-1];
                answer[i] = max({prod1, prod2, 0*1LL});
            }
        }
        return answer;
        
    }
};
```
['Tree', 'Depth-First Search', 'Sorting', 'C++']