2646. 最小化旅行的价格总和

难度困难

现有一棵无向、无根的树，树中有 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

# 暴力 DFS 每一条路径

cnt[i] : 有几次旅行包含节点 i，即每个点被经过多少次

因为最终统计的是所有旅行的最小价格和
每次旅行对经过节点的贡献

知道了每个点被经过多少次就可以仿照 337. 打家劫舍 III 来做了

$dfs(u, 0)$ ：以 u 为根节点不选择（不折半）的最小价格和

$dfs(u, 1)$ ：以 u 为根节点选择（折半）的最小价格和

当前点要么选（折半），要么不选（不折半）

选（折半），其相邻节点不能选择（不折半）
- $binary = cnt[i] * price[i] / 2 + dfs(v, 0)$
不选，其相邻节点可以选择，也可以不选择
- $noBinary = price[i] + max(dfs(v, 0), dfs(v, 1));$

当前根节点的最小价格和： $ans = max(sel, noSel)$

	class Solution {
	List<Integer>[] tree;
	int[] cnt, price;

	public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
	tree = new List[n];
	cnt = new int[n];
	this.price = price;
	for (int i = 0; i < n; i++) {
	tree[i] = new ArrayList<>();
	}
	for (int[] edge : edges) {
	tree[edge[0]].add(edge[1]);
	tree[edge[1]].add(edge[0]);
	}
	for (int[] trip : trips) {
	helper(trip[0], -1, trip[1]);
	}
	int[] ans = dfs(0, -1);
	return Math.min(ans[0], ans[1]);
	}

	// 计算每个点被经过多少次
	public boolean helper(int x, int fa, int dest) {
	if (x == dest) {
	cnt[x]++;
	return true;
	}
	List<Integer> list = tree[x];
	for (Integer y : list) {
	if (y != fa) {
	if (helper(y, x, dest)) {
	cnt[x]++;
	return true;
	}
	}
	}
	return false;
	}

	// 树形 dp, [不折半，折半]
	public int[] dfs(int x, int fa) {
	List<Integer> list = tree[x];
	int binary = cnt[x] * price[x] / 2;
	int noBinary = cnt[x] * price[x];
	for (Integer y : list) {
	if (y == fa) {
	continue;
	}
	int[] next = dfs(y, x);
	// 要么折半，要么不折半
	binary += next[0];
	noBinary += Math.min(next[0], next[1]);
	}
	return new int[]{noBinary, binary};
	}
	}

# 复杂度分析

时间复杂度 ： $O(nm)$ ，其中 $m$ 为 $trips$ 的长度
空间复杂度 ： $O(n)$

# 树上差分 +Tarjan 离线 LCA

前置知识：并查集，并查集模板 - 冗余连接

从解法一可以看出，计算每个点被经过多少次 cnt[i] ，需要 $O(n^2)$ 的复杂度。有没有什么办法可以降低为线性复杂度。那就是树上差分 + tarjan

一：差分数组

先看一个问题：对于数组 a

操作一：对区间 [i, j] 每个元素加上某个数 v

操作二：对操作一重复 n 次， 1 <= a.length <= n <= 1e6

首先想到的是对区间 [i, j] 每个元素遍历一次， $O(n ^ 2)$ 的时间复杂度。不行！

所以需要差分数组 diff

diff[i] = a[i + 1] - a[i]

我们需要将区间 [1, 4] 统一加上 1

diff[0] += 1 ， diff[4] -= 1 即可

此时 a[i + 1] = diff[i] + a[i]

如上可以发现，只需要更新该区间两端的差分即可。

二：树上差分

我们需要对路径 3 ~ 6 上的每一点加 1

由于这是一颗树，所以 3 ~ 6 的最优路径必然是唯一的， 3 ~ 1 再 1 ~ 6 ，节点 1 就是节点 3 和节点 6 的最近公共祖先 lca

路径 [3, 2] ： diff[3] += 1, diff[1] -= 1

路径 [6, 1] ： diff[6] += 1, diff[0] -= 1

如何求访问次数呢？只需要自底向上的对差分数组求前缀和即可

例如：节点 1 的访问次数就是 + 1 + 1 - 1 = 1 次。

三：Tarjan 离线 LCA

如何求解【多组】两个节点的 LCA 呢？可采用 Tarjan 离线 LCA 在线性复杂度计算出 LCA。

如下所示，求解节点 7 与节点 8 的 lca

采用自底向上遍历节点：[7, 3, 8, 10, 9, 2]

如下图所示，递归返回至节点 2，此时节点 7 和节点 3 的父节点就是节点 2

并查集 merge(7, 3) -> merge(3, 2) 。

如下图所示，此时遍历到节点 8，节点 8 必然由祖先节点 2 衍生出来。

我们不需要再遍历节点 2 的左子树，直接获取节点 7 的父节点：节点 2（ find(7) ）。

此时节点 2 就是节点 7 和节点 8 的 lca

如下图所示，此时遍历到节点 5，节点 5 必然由祖先节点 1 衍生出来

节点 2 以及其子树的父节点都指向节点 1

我们需要求解节点 3 与节点 5 的 lca。此时我们不需要再遍历节点 1 的左子树，

只需要满足节点 3 被遍历过，若没有遍历过，则必然为节点 5 的子树或者在其右边。

直接获取节点 3 的父节点：节点 1（ find(3) ）

此时节点 1 就是节点 3 和节点 5 的 lca

四：Tarjan 离线 LCA + 树上差分

经过 tarjan 求出相应的两个节点 lca 后的差分数组：

在进行一次 dfs 自底向上对差分数组进行累加，即可计算出每个节点经过的次数 cnt

可以发现，由于是自底向上的遍历，树形 dp 计算最小价格和与计算 cnt 可以同时进行。

	class Solution {
	List<Integer>[] tree, ts;
	int[] diff, price, pa, father, visited;

	public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
	tree = new List[n];
	ts = new List[n];
	visited = new int[n];
	diff = new int[n];
	this.price = price;
	pa = new int[n];
	for (int i = 0; i < n; i++) {
	pa[i] = i;
	tree[i] = new ArrayList<>();
	ts[i] = new ArrayList<>();
	}
	for (int[] edge : edges) {
	tree[edge[0]].add(edge[1]);
	tree[edge[1]].add(edge[0]);
	}
	for (int[] trip : trips) {
	ts[trip[0]].add(trip[1]);
	// 相等会重复
	if (trip[0] != trip[1]) {
	ts[trip[1]].add(trip[0]);
	}
	}
	father = new int[n];
	tarjan(0, -1);
	int[] ans = dfs(0, -1);
	return Math.min(ans[0], ans[1]);
	}

	public int find(int x) {
	if (x == pa[x]) {
	return x;
	}
	// 路径压缩
	return pa[x] = find(pa[x]);
	}

	public void tarjan(int x, int fa) {
	father[x] = fa;
	List<Integer> list = tree[x];
	visited[x] = 1;
	for (Integer y : list) {
	// 没有被访问过
	if (visited[y] == 0) {
	tarjan(y, x);
	// 合并，y 及其子树的父节点指向 x
	pa[y] = x;
	}
	}
	// 求解节点 x 与节点 y 的 lca，并更新差分数组
	for (Integer y : ts[x]) {
	//y 被遍历过，此时 y 及其子树的父节点都指向 lca 或者路径就是自身
	if (y == x \|\| visited[y] == 2) {
	int lca = find(y);
	diff[y]++;
	diff[lca]--;

	diff[x]++;
	// 获取 lca 的父节点
	// - 此时 lca 必然为当前根节点
	int f = father[lca];
	//f == -1, 说明是根节点 0
	if (f >= 0) {
	diff[f]--;
	}
	}
	}
	visited[x] = 2;
	}

	// 树形 dp, [不折半，折半]
	public int[] dfs(int x, int fa) {
	List<Integer> list = tree[x];
	int binary = 0;
	int noBinary = 0;
	for (Integer y : list) {
	if (y == fa) {
	continue;
	}
	int[] next = dfs(y, x);
	// 要么折半，要么不折半
	binary += next[0];
	noBinary += Math.min(next[0], next[1]);
	// 对差分数组自底向上的求和，即为最终节点的经过次数 cnt
	diff[x] += diff[y];
	}
	int cnt = diff[x];
	binary += cnt * price[x] / 2;
	noBinary += cnt * price[x];
	return new int[]{noBinary, binary};
	}
	}

# 复杂度分析

时间复杂度 ： $O(n + m\alpha)$ ，其中 $m$ 为 $trips$ 的长度， $\alpha$ 为并查集的常数，可视为 $O(1)$
空间复杂度 ： $O(n+m)$

动态规划困难并查集树树形 dp 深度优先搜索

# 暴力 DFS 每一条路径

# 复杂度分析

# 树上差分 +Tarjan 离线 LCA

# 复杂度分析

树形dp模板 打家劫舍Ⅲ

滑动子数组的美丽值

树形dp模板打家劫舍Ⅲ