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完整代码如下：
代码语言：javascript复制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)
}
在这里插入图片描述
