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 edges.length == n – 1
0 edges 表示一棵有效的树
price.length == n
price[i] 是一个偶数
1 1 0
2思路：
深度优先搜索 + 动态规划,
为了使旅行的价格总和最小，那么每次旅行的路径必定是最短路径。根据题意，每次旅行 trips[i] 都是独立的，因此我们可以依次开始旅行 trips[i]，并且用数组 count记录节点在旅行中被经过的次数。记旅行 trips[i]的起点和终点分别为 starti和 endi，那么我们以 starti为树的根节点，对树进行深度优先搜索，对于如果节点 nodetextit{node}node 的子树（包含它本身）包含节点 endi ，那么我们将 count[node] 加一。
3java代码：
class Solution {
private List[] 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 = 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};
}
}服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
点餐外卖多门店多商家积分商城小程序开源版开发 点餐外卖多门店多商家积分商城小程序是一款提供点餐、外卖、多门店、多商家积分商城功能的小程序。以下是该小程序的功能介绍： 点餐功能：用户可以通过小程序浏览不同门店的菜单，选择自己喜欢的菜品进行点餐。用户可以根据自己的…
