题目 #
There exists an undirected and unrooted tree with n nodes indexed from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
Each node has an associated price. You are given an integer array price, where price[i] is the price of the ith node.
The price sum of a given path is the sum of the prices of all nodes lying on that path.
Additionally, you are given a 2D integer array trips, where trips[i] = [starti, endi] indicates that you start the ith trip from the node starti and travel to the node endi by any path you like.
Before performing your first trip, you can choose some non-adjacent nodes and halve the prices.
Return the minimum total price sum to perform all the given trips.
Example 1:
Input: n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
Output: 23
Explanation: The diagram above denotes the tree after rooting it at node 2. The first part shows the initial tree and the second part shows the tree after choosing nodes 0, 2, and 3, and making their price half.
For the 1st trip, we choose path [0,1,3]. The price sum of that path is 1 + 2 + 3 = 6.
For the 2nd trip, we choose path [2,1]. The price sum of that path is 2 + 5 = 7.
For the 3rd trip, we choose path [2,1,3]. The price sum of that path is 5 + 2 + 3 = 10.
The total price sum of all trips is 6 + 7 + 10 = 23.
It can be proven, that 23 is the minimum answer that we can achieve.
Example 2:
Input: n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
Output: 1
Explanation: The diagram above denotes the tree after rooting it at node 0. The first part shows the initial tree and the second part shows the tree after choosing node 0, and making its price half.
For the 1st trip, we choose path [0]. The price sum of that path is 1.
The total price sum of all trips is 1. It can be proven, that 1 is the minimum answer that we can achieve.
Constraints:
- 1 <= n <= 50
- edges.length == n - 1
- 0 <= ai, bi <= n - 1
- edges represents a valid tree.
- price.length == n
- price[i] is an even integer.
- 1 <= price[i] <= 1000
- 1 <= trips.length <= 100
- 0 <= starti, endi <= n - 1
思路1 dfs+dfs #
分析 #
- 因为是无环树，直接使用dfs找路径更简单，用bfs复杂了
- 路径是固定的，那么就是将所有的点走了几次统计出来，然后找最小的价格即可
- 选几个节点降价，并且要求不相邻，那么也是用dfs
- 从某个点开始，选和不选有两种价格，对于下一个相邻点也有选和不选两个价格
- 选当前点，那么就是下个相邻的点一定不能选
- 不选当前点，那么下个相邻的点可选可不选，找最小的即可
- 最终返回选和不选当前点的较小的那个即可
代码 #
1func min(a, b int) int {
2 if a > b {
3 return b
4 }
5 return a
6}
7
8func minimumTotalPrice(n int, edges [][]int, price []int, trips [][]int) int {
9 rel := make([][]int, n)
10 for _, v := range edges {
11 x, y := v[0], v[1]
12 rel[x] = append(rel[x], y)
13 rel[y] = append(rel[y], x)
14 }
15 // 因为只有一条路，所以深度优先
16 // 起点、终点、上一步（因为不存在环路，所以判断不回来即可）
17 var dfs func(s, e, last int) bool
18 cnt := make(map[int]int)
19 dfs = func(s, e, last int) bool {
20 if s == e {
21 cnt[e]++
22 return true
23 }
24 for _, v := range rel[s] {
25 if v != last && dfs(v, e, s) {
26 cnt[s]++
27 return true
28 }
29 }
30 return false
31 }
32 for _, v := range trips {
33 dfs(v[0], v[1], -1)
34 }
35
36 // 单向，使用last即可防止回路
37 // 返回选和不选的两个大小
38 var dfs1 func(s, last int) (nch, ch int)
39 dfs1 = func(s, last int) (nch int, ch int) {
40 nch = cnt[s] * price[s]
41 ch = nch / 2
42 for _, v := range rel[s] {
43 if v == last {
44 continue
45 }
46 vnch, vch := dfs1(v, s)
47 ch += vnch // 当前选中了就只能选择没选中的
48 nch += min(vnch, vch)
49 }
50 return
51 }
52 // 随便找一个要走的点开始遍历
53 nch, ch := dfs1(trips[0][0], -1)
54 return min(nch, ch)
55}
思路2 树上差分+dfs #
分析 #
- 后面的计算最小值没什么好说的，但是前面的计算每个点走过的次数倒是可以优化
- cnt每个trip查询一遍整体时间复杂度为 $O(nq)$，那么可以使用树上差分配合Tarjan算法的LCA处理将此时间复杂度降到 $O(n + q)$
- 树上差分和Tarjan算法处理LCA自己搜一下，也可以看 Tarjan处理LCA 和 树上差分
代码 #
1func minimumTotalPrice1(n int, edges [][]int, price []int, trips [][]int) int {
2 rel := make([][]int, n)
3 for _, v := range edges {
4 x, y := v[0], v[1]
5 rel[x] = append(rel[x], y)
6 rel[y] = append(rel[y], x)
7 }
8
9 // 树上差分计算cnt
10 diff := make([]int, n)
11 // 把查询都取出来，一次遍历全部查一遍
12 qs := make(map[int][]int)
13 for _, v := range trips {
14 x, y := v[0], v[1]
15 qs[x] = append(qs[x], y)
16 if x != y {
17 qs[y] = append(qs[y], x)
18 }
19 }
20 // 并查集模板
21 uf := make([]int, n)
22 for i := range uf {
23 uf[i] = i
24 }
25 find := func(x int) int {
26 ap := uf[x]
27 // 找到最终节点
28 for ap != uf[ap] {
29 ap = uf[ap]
30 }
31 // 沿途都赋值最终节点
32 for x != ap {
33 uf[x], x = ap, uf[x]
34 }
35 return ap
36 }
37 // 把a的子集合并到b上，如果b是树根节点，a的所有子节点查找都会查找到b
38 merge := func(a, b int) {
39 uf[find(a)] = find(b)
40 }
41 // Tarjan算法计算公共祖先
42 color := make([]bool, n)
43 father := make([]int, n) // 每个节点的父节点
44 var tarjan func(a, fa int)
45 tarjan = func(a, fa int) {
46 father[a] = fa
47 for _, v := range rel[a] {
48 if v == fa {
49 continue
50 }
51 tarjan(v, a)
52 // 进去出来后，将v为根节点的子树设置公共祖先为a
53 merge(v, a)
54 }
55
56 // 查一下有没有要求的LCA
57 for _, v := range qs[a] {
58 if v != a && !color[v] {
59 // 自己走到自己是可以计算的，要判断
60 // v还没走到，继续
61 continue
62 }
63 lca := find(v)
64 diff[a]++
65 diff[v]++
66 diff[lca]--
67 if lcaFa := father[lca]; lcaFa >= 0 {
68 diff[lcaFa]--
69 }
70 }
71 color[a] = true // a被灌了岩浆，也就是a的子树走完了，要向上走了
72 }
73 // 从0向下走
74 tarjan(0, -1)
75
76 // dfs，同时计算差分
77 // 返回选和不选的两个大小
78 var dfs1 func(s, fa int) (nch, ch, cnt int)
79 dfs1 = func(s, fa int) (nch, ch, cnt int) {
80 cnt = diff[s]
81 for _, v := range rel[s] {
82 if v == fa {
83 continue
84 }
85 vnch, vch, ccnt := dfs1(v, s)
86 ch += vnch // 当前选中了就只能选择没选中的
87 nch += min(vnch, vch)
88 cnt += ccnt // 当前节点cnt为自己的差分加上所有子节点cnt之和
89 }
90 nch += cnt * price[s]
91 ch += cnt * price[s] / 2
92 return
93 }
94 // 从根节点遍历
95 nch, ch, _ := dfs1(0, -1)
96 return min(nch, ch)
97}