2023-10-04：用go语言，现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号

给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，

其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。

给定路径的 价格总和 是该路径上所有节点的价格之和。

另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示

从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。

在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。

返回执行所有旅行的最小价格总和。

输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]。

输出：23。

来自左程云。

答案2023-10-04：

大体过程如下：

1.构建图：根据输入的edges构建无向图，使用邻接表存储每个节点的邻居节点。

2.初始化查询数组：根据trips初始化查询数组，将每个旅行的起点和终点加入到对应节点的查询数组中。

3.初始化并查集：初始化一个并查集，用于保存节点的父节点信息和标签。将每个节点的父节点初始化为自身，标签初始化为-1。

4.进行Tarjan算法：从根节点开始遍历树，使用递归的方式进行深度优先搜索。

• 对于每个节点cur，记录其父节点father。• 遍历cur的邻居节点next，如果next不等于father，进行递归操作。• 递归操作结束后，将cur和next节点合并，设置它们的标签为cur。• 对于cur节点的查询数组中的每个查询，如果查询的终点的标签不为-1，说明该查询经过cur节点，记录查询的终点标签为最低公共祖先节点。

5.计算每个节点的旅行个数：遍历旅行数组，统计每个节点作为起点或终点的旅行个数。

• 对于每个旅行，起点和终点的旅行个数加1，最低公共祖先节点的旅行个数减1。• 如果最低公共祖先节点的父节点不为-1，最低公共祖先节点的父节点的旅行个数减1。

6.使用深度优先搜索计算价格总和：从根节点开始，使用递归的方式进行深度优先搜索。

• 对于每个节点cur，计算不选择减半价格的情况下的总价格no和选择减半价格的情况下的总价格• 遍历cur的邻居节点next，如果next不等于father，进行递归操作。• 更新no和yes的值。

7.返回最小价格总和：取no和yes中较小的值作为最小价格总和。

总的时间复杂度：O(n)（遍历节点和邻居节点） + O(m)（遍历查询数组） + O(n)（遍历旅行数组） + O(n)（遍历节点和邻居节点） = O(n + m)

总的额外空间复杂度：O(n)（存储图） + O(m)（存储查询数组） + O(n)（存储父节点信息） + O(n)（存储旅行个数） + O(n)（存储价格总和） = O(n + m)

go完整代码如下：

package mainimport (    "fmt"    "math")func minimumTotalPrice(n int, edges [][]int, price []int, trips [][]int) int {    graph := make([][]int, n)    queries := make([][][]int, n)    for i := 0; i < n; i++ {        graph[i] = make([]int, 0)        queries[i] = make([][]int, 0)    }    for _, edge := range edges {        graph[edge[0]] = append(graph[edge[0]], edge[1])        graph[edge[1]] = append(graph[edge[1]], edge[0])    }    m := len(trips)    lcs := make([]int, m)    for i := 0; i < m; i++ {        if trips[i][0] == trips[i][1] {            lcs[i] = trips[i][0]        } else {            queries[trips[i][0]] = append(queries[trips[i][0]], []int{trips[i][1], i})            queries[trips[i][1]] = append(queries[trips[i][1]], []int{trips[i][0], i})        }    }    uf := &UnionFind{}    uf.init(n)    fathers := make([]int, n)    tarjan(graph, 0, -1, uf, queries, fathers, lcs)    cnts := make([]int, n)    for i := 0; i < m; i++ {        cnts[trips[i][0]]++        cnts[trips[i][1]]++        cnts[lcs[i]]--        if fathers[lcs[i]] != -1 {            cnts[fathers[lcs[i]]]--        }    }    dfs(graph, 0, -1, cnts)    ans := dp(graph, 0, -1, cnts, price)    return int(math.Min(float64(ans[0]), float64(ans[1])))}func tarjan(graph [][]int, cur int, father int, uf *UnionFind, queries [][][]int, fathers []int, lcs []int) {    fathers[cur] = father    for _, next := range graph[cur] {        if next != father {            tarjan(graph, next, cur, uf, queries, fathers, lcs)            uf.union(cur, next)            uf.setTag(cur, cur)        }    }    for _, query := range queries[cur] {        tag := uf.getTag(query[0])        if tag != -1 {            lcs[query[1]] = tag        }    }}func dfs(graph [][]int, cur int, father int, cnts []int) {    for _, next := range graph[cur] {        if next != father {            dfs(graph, next, cur, cnts)            cnts[cur] += cnts[next]        }    }}func dp(graph [][]int, cur int, father int, cnts []int, price []int) []int {    no := price[cur] * cnts[cur]    yes := (price[cur] / 2) * cnts[cur]    for _, next := range graph[cur] {        if next != father {            nextAns := dp(graph, next, cur, cnts, price)            no += int(math.Min(float64(nextAns[0]), float64(nextAns[1])))            yes += nextAns[0]        }    }    return []int{no, yes}}type UnionFind struct {    father []int    size   []int    tag    []int    help   []int}func (uf *UnionFind) init(n int) {    uf.father = make([]int, n)    uf.size = make([]int, n)    uf.tag = make([]int, n)    uf.help = make([]int, n)    for i := 0; i < n; i++ {        uf.father[i] = i        uf.size[i] = 1        uf.tag[i] = -1    }}func (uf *UnionFind) find(i int) int {    size := 0    for i != uf.father[i] {        uf.help[size] = i        i = uf.father[i]        size++    }    for size > 0 {        size--        uf.father[uf.help[size]] = i    }    return i}func (uf *UnionFind) union(i, j int) {    fi := uf.find(i)    fj := uf.find(j)    if fi != fj {        if uf.size[fi] >= uf.size[fj] {            uf.father[fj] = fi            uf.size[fi] += uf.size[fj]        } else {            uf.father[fi] = fj            uf.size[fj] += uf.size[fi]        }    }}func (uf *UnionFind) setTag(i, t int) {    uf.tag[uf.find(i)] = t}func (uf *UnionFind) getTag(i int) int {    return uf.tag[uf.find(i)]}func main() {    n := 4    edges := [][]int{{0, 1}, {1, 2}, {1, 3}}    price := []int{2, 2, 10, 6}    trips := [][]int{{0, 3}, {2, 1}, {2, 3}}    result := minimumTotalPrice(n, edges, price, trips)    fmt.Println(result)}

在这里插入图片描述