Go solution | DFS
Complexity\n- Time complexity:\nO(n log n)\n\n- Space complexity:\nO(n)\n\n# Code\n\nvar result []int64\n\nfunc dfs(adj [][]int, cost []int, root, par int) []in
# Complexity\n- Time complexity:\n$$O(n log n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nvar result []int64\n\nfunc dfs(adj [][]int, cost []int, root, par int) []int64 {\n    rootCosts := []int64{int64(cost[root])}\n\n    // Traverse all the children of root\n    // ans accumulate the costs\n    for _, c := range adj[root] {\n        if c == par {\n            continue\n        }\n\n        currCost := dfs(adj, cost, c, root)\n        for _, curC := range currCost {\n            rootCosts = append(rootCosts, curC)\n        }\n    }\n\n    // Now sort the root costs as we need top 3 and bottom 2\n    slices.Sort(rootCosts)\n    slices.Reverse(rootCosts)   // We want sorted to be decresing\n\n    n := len(rootCosts)\n\n    // If we don\'t have 3 costs then this must be a leaf node\n    // just add 1 for thier result\n    if n < 3 {\n        result[root] = 1\n        return rootCosts\n    }\n\n    // We can take 0th, 1st and 2nd or we can take 0th, n-1, n-2\n    // whichever gives the greater result\n    if rootCosts[1] * rootCosts[2] > rootCosts[n-1] * rootCosts[n-2] {\n        result[root] = rootCosts[0] * rootCosts[1] * rootCosts[2]\n    } else {\n        result[root] = rootCosts[0] * rootCosts[n-1] * rootCosts[n-2]\n    }\n\n    // If after multiplying this gives negative number, then we have to set it 0\n    result[root] = max(result[root], 0)\n\n    // If we have 5 or more root costs, return top 3 and bottom 2\n    if n <= 5 {\n        return rootCosts\n    }\n\n    return []int64{rootCosts[0], rootCosts[1], rootCosts[2], rootCosts[n-2], rootCosts[n-1]}\n}\n\nfunc placedCoins(edges [][]int, cost []int) []int64 {\n    n := len(cost)\n    result = make([]int64, n)\n    adj := make([][]int, n)\n    for _, edge := range edges {\n        u := edge[0]\n        v := edge[1]\n\n        adj[u] = append(adj[u], v)\n        adj[v] = append(adj[v], u)\n    }\n\n    dfs(adj, cost, 0, -1)\n    return result\n}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n```
['Depth-First Search', 'Go']