2023-10-04：用 go 语言，现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edge

作者：福大大架构师每日一题

2023-10-04
北京
本文字数：2744 字
阅读完需：约 9 分钟

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 < 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)}