本文主要是介绍【教3妹学编程-算法题】最小化旅行的价格总和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
3妹：2哥2哥，你有没有看到新闻， 有人中了2.2亿彩票大奖！
2哥 : 看到了，2.2亿啊， 一生一世也花不完。
3妹：为啥我就中不了呢，不开心呀不开心。
2哥 : 得了吧，你又不买彩票，还是脚踏实地的好~
3妹：小富靠勤，中富靠德，大富靠命， 可能是我命不好。
2哥 : 话说如果你有了钱，想要干嘛呀？
3妹：旅行，到处去旅行
2哥：就知道会有这一项， 我今天看到一个关于旅行的题目，让我也来考考你吧~
题目：
现有一棵无向、无根的树，树中有 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
思路：
深度优先搜索 + 动态规划,
为了使旅行的价格总和最小，那么每次旅行的路径必定是最短路径。根据题意，每次旅行 trips[i] 都是独立的，因此我们可以依次开始旅行 trips[i]，并且用数组 count记录节点在旅行中被经过的次数。记旅行 trips[i]的起点和终点分别为 starti和 endi，那么我们以 starti为树的根节点，对树进行深度优先搜索，对于如果节点 node\textit{node}node 的子树（包含它本身）包含节点 endi ，那么我们将 count[node] 加一。
java代码：
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};}
}这篇关于【教3妹学编程-算法题】最小化旅行的价格总和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
