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

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 main

import (

"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 

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 

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 

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 

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)

}

在这里插入图片描述