Golang Solution ||| Beats 100% ||| With explanations!👍
Intuition\nOf course, this is a graph + DFS construction problem.\n\n# Approach\nWe build a graph as usual - graph is an object of map type with []int key. In e
# Intuition\nOf course, this is a graph + DFS construction problem.\n\n# Approach\nWe build a graph as usual - **graph is an object of map type with []int key. In each graph key (v) we store all vertices to which we can go from the vertex v**\n\nThe graph is constructed as follows: \n```\n    graph := make(map[int][]int)  \n    for _, egde := range edges { \n        graph[egde[0]] = append(graph[egde[0]], egde[1]) \n        graph[egde[1]] = append(graph[egde[1]], egde[0]) \n    } \n```\n  \n\nLet\'s also introduce the use array, the ans array. Use will denote the vertices we have been to. This is done so that from vertex v we don\'t go to the parent. And ans - here we will store the answers \n\n# DFS \n\n**Why not BFS?** Because we need an answer for a subtree, not for a line of vertices with the same depth.\nWhat do we return in DFS?\n\n**Let\'s for each DFS, we will import a list of 3 minimum negative cost vertices for the subtree and a list of 3 maximum positive cost vertices for the subtree.**\n\nI will call the list of negative stabilities otr, positive stabilities pol\n**Maximal product of storing such an array:** $$max(otr[0] * otr[1] * pol[0], pol[1] * pol[2] * pol[3]).$$\n\n**For each subarray V we will recognize its subarrays otr and pol. Then add these arrays to ours from the DFS function, sort them as needed, and discard unnecessary ones.** In this way, we save memory and the time needed for sorting.\n\nBefore knowing the answer for ans[v] we need to proify the lengths of the otr and pol arrays to prevent errors. \n\n**If my solution was helpful, don\'t forget to upvote \uD83D\uDDA4**\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nfunc max(a, b int64) int64 {\n    if a > b {\n        return a\n    }\n    return b\n}\n\nfunc min(a, b int) int {\n    if a < b {\n        return a\n    }\n    return b\n}\n \nfunc dfs(v int, graph *map[int][]int, use *[]bool, cost *[]int, ans *[]int64) [][]int64 {\n    // We say the vertex can no longer be used.\n    (*use)[v] = true\n    pol := []int64{}\n    otr := []int64{}\n    // Add cost[v] to the desired array\n    if (*cost)[v] < 0 {\n        otr = append(otr, int64((*cost)[v]))\n    } else {\n        pol = append(pol, int64((*cost)[v]))\n    }\n    for _, nextV := range (*graph)[v] {\n        if !(*use)[nextV] {\n            // Define new array otr and pol\n            ansNextV := dfs(nextV, graph, use, cost, ans)\n            pol = append(pol, ansNextV[0]...)\n            sort.Slice(pol, func(i, j int) bool {\n                return pol[i] >= pol[j]\n            })\n            pol = pol[:min(3, len(pol))]\n            otr = append(otr, ansNextV[1]...)\n            sort.Slice(otr, func(i, j int) bool {\n                return otr[i] <= otr[j]\n            })\n            otr = otr[:min(3, len(otr))]\n        } \n    }\n    // If lens of otr and pol arrays\n    if len(pol) + len(otr) < 3 {\n        (*ans)[v] = 1\n    } else {\n        var mxProiz int64 \n        if len(pol) == 0 {\n            mxProiz = otr[0] * otr[1] * otr[2]\n        } else if len(otr) == 0 {\n            mxProiz = pol[0] * pol[1] * pol[2]\n        } else if len(otr) == 1 && len(pol) == 2 {\n            mxProiz = otr[0] * pol[0] * pol[1]\n        } else if len(otr) >= 2 && len(pol) < 3 {\n            mxProiz = otr[0] * otr[1] * pol[0]\n        } else if len(otr) == 1 && len(pol) >= 3 {\n            mxProiz = pol[0] * pol[1] * pol[2]\n        } else {\n            potentialMxProiz1 := otr[0] * otr[1] * pol[0]\n            potentialMxProiz2 := pol[0] * pol[1] * pol[2]\n            mxProiz = max(potentialMxProiz1, potentialMxProiz2)\n        }\n        (*ans)[v] = mxProiz\n    }\n    // Define the answer for ans[v]\n    if (*ans)[v] < 0 {\n        (*ans)[v] = 0\n    }\n    return [][]int64{pol, otr}\n}\n\n\nfunc placedCoins(edges [][]int, cost []int) []int64 {\n    n := len(cost)\n    ans := make([]int64, n)\n    // Build the graph\n    graph := make(map[int][]int) \n    for _, egde := range edges {\n        graph[egde[0]] = append(graph[egde[0]], egde[1])\n        graph[egde[1]] = append(graph[egde[1]], egde[0])\n    }\n    use := make([]bool, n)\n    // Start DFS\n    dfs(0, &graph, &use, &cost, &ans)\n    return ans\n}\n```\n![Upvote Please.jpeg](https://assets.leetcode.com/users/images/7cc189b5-4ed9-4cb3-ac22-9c1e6efb0f79_1703347913.913169.jpeg)\n
['Depth-First Search', 'Graph', 'Go']