💥💥 Beats 100% on runtime and memory [EXPLAINED]
IntuitionThe problem is about traversing a tree (represented by a graph), where each node has a cost, and I need to calculate the maximum number of coins I can
# Intuition
The problem is about traversing a tree (represented by a graph), where each node has a cost, and I need to calculate the maximum number of coins I can collect starting from the root node. The approach involves exploring all the child nodes of each node, calculating the maximum costs, and deciding how many coins each node should have based on the values of its children.

# Approach
I first build the graph using an adjacency list where each node points to its neighbors, then I use DFS to traverse the tree, and at each node, I calculate the maximum costs from its children, sort them, and decide the node's coin value based on the top 3 maximum costs, and I return the result after processing all nodes.

# Complexity
- Time complexity:
O(n * log(n)), where n is the number of nodes, because for each node I perform a DFS, and for each node, I sort the costs of its children.

- Space complexity:
O(n), because I use extra space to store the graph and the coin counts for each node.

# Code
```typescript []
let placedCoins = (edges: number[][], cost: number[]): number[] => {
    const n = cost.length;
    const graph: number[][] = Array.from({ length: n }, () => []);
    const coins: number[] = new Array(n).fill(0);
    
    // Building the Graph
    for (const edge of edges) {
        const [u, v] = edge;
        graph[u].push(v);
        graph[v].push(u);
    }
    
    // Core Logic
    DFS(graph, cost, coins, 0, -1);
    return coins;
};

let DFS = (graph: number[][], cost: number[], coins: number[], node: number, parent: number): number[] => {
    let subtree = 1;
    let maxCosts: number[] = [cost[node]];
    
    for (const cn of graph[node]) {
        if (cn !== parent) {
            const arr = DFS(graph, cost, coins, cn, node);
            maxCosts.push(...arr);
        }
    }
    
    maxCosts.sort((a, b) => b - a);
    
    if (maxCosts.length < 3) {
        coins[node] = 1;
    } else {
        const size = maxCosts.length;
        coins[node] = Math.max((maxCosts[0] * maxCosts[1] * maxCosts[2]), (maxCosts[0] * maxCosts[size - 1] * maxCosts[size - 2]));
        coins[node] = Math.max(0, coins[node]);
        
        if (maxCosts.length >= 5) {
            return [maxCosts[0], maxCosts[1], maxCosts[2], maxCosts[size - 2], maxCosts[size - 1]];
        }
    }
    
    return maxCosts;
};

```
['Math', 'Divide and Conquer', 'Dynamic Programming', 'Backtracking', 'Depth-First Search', 'Graph', 'Topological Sort', 'Heap (Priority Queue)', 'Combinatorics', 'TypeScript']