3妹：2哥2哥，你有没有看到新闻， 有人中了2.2亿彩票大奖！
2哥 : 看到了，2.2亿啊， 一生一世也花不完。
3妹：为啥我就中不了呢，不开心呀不开心。
2哥 : 得了吧，你又不买彩票，还是脚踏实地的好~
3妹：小富靠勤，中富靠德，大富靠命， 可能是我命不好。
2哥 : 话说如果你有了钱，想要干嘛呀？
3妹：旅行，到处去旅行
2哥：就知道会有这一项， 我今天看到一个关于旅行的题目，让我也来考考你吧~
1题目：
现有一棵无向、无根的树，树中有 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 。
在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。
返回执行所有旅行的最小价格总和。
示例 1：
输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出：23
解释：
上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。
示例 2：
输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出：1
解释：
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。
第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。
所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。
提示：
1 <= n <= 50
edges.length == n - 1
0 <= ai, bi <= n - 1
edges 表示一棵有效的树
price.length == n
price[i] 是一个偶数
1 <= price[i] <= 1000
1 <= trips.length <= 100
0 <= starti, endi <= n - 1
2思路：
深度优先搜索 + 动态规划,
为了使旅行的价格总和最小，那么每次旅行的路径必定是最短路径。根据题意，每次旅行 trips[i] 都是独立的，因此我们可以依次开始旅行 trips[i]，并且用数组 count记录节点在旅行中被经过的次数。记旅行 trips[i]的起点和终点分别为 starti和 endi，那么我们以 starti为树的根节点，对树进行深度优先搜索，对于如果节点 node\textit{node}node 的子树（包含它本身）包含节点 endi ，那么我们将 count[node] 加一。
3java代码：
class Solution {
private List<Integer>[] g, qs;
private int[] diff, father, color, price;
public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList<>());
for (var e : edges) {
int x = e[0], y = e[1];
g[x].add(y);
g[y].add(x); // 建树
}
qs = new ArrayList[n];
Arrays.setAll(qs, e -> new ArrayList<>());
for (var t : trips) {
int x = t[0], y = t[1];
qs[x].add(y); // 路径端点分组
if (x != y) qs[y].add(x);
}
pa = new int[n];
for (int i = 1; i < n; ++i)
pa[i] = i;
diff = new int[n];
father = new int[n];
color = new int[n];
tarjan(0, -1);
this.price = price;
var p = dfs(0, -1);
return Math.min(p[0], p[1]);
}
// 并查集模板
private int[] pa;
private int find(int x) {
if (pa[x] != x)
pa[x] = find(pa[x]);
return pa[x];
}
private void tarjan(int x, int fa) {
father[x] = fa;
color[x] = 1; // 递归中
for (int y : g[x])
if (color[y] == 0) { // 未递归
tarjan(y, x);
pa[y] = x; // 相当于把 y 的子树节点全部 merge 到 x
}
for (int y : qs[x])
// color[y] == 2 意味着 y 所在子树已经遍历完
// 也就意味着 y 已经 merge 到它和 x 的 lca 上了
if (y == x || color[y] == 2) { // 从 y 向上到达 lca 然后拐弯向下到达 x
++diff[x];
++diff[y];
int lca = find(y);
--diff[lca];
int f = father[lca];
if (f >= 0) {
--diff[f];
}
}
color[x] = 2; // 递归结束
}
private int[] dfs(int x, int fa) {
int notHalve = 0, halve = 0, cnt = diff[x];
for (int y : g[x])
if (y != fa) {
var p = dfs(y, x); // 计算 y 不变/减半的最小价值总和
notHalve += Math.min(p[0], p[1]); // x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值
halve += p[0]; // x 减半，那么 y 只能不变
cnt += p[2]; // 自底向上累加差分值
}
notHalve += price[x] * cnt; // x 不变
halve += price[x] * cnt / 2; // x 减半
return new int[]{notHalve, halve, cnt};
}
}