【题解】CF1000G：Two-Paths_two paths题解-CSDN博客

本文链接：https://blog.csdn.net/ModestCoder_/article/details/108781536

本文介绍了如何使用倍增动态规划（DP）方法解决类似《保卫王国》的问题，详细讲解了f、dp和g数组的更新规则，并提供了代码实现，重点在于理解并应用多点到点的路径查询，包括祖先路径和最短路径计算.

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

原题传送门
这道题目和保卫王国非常的相似
倍增dp

记 $l$ 为 $w (u, v)$
$f_u$ 表示，从 $u$ 出发回到 $u$ ，走以 $u$ 为根的子树的答案
$f_u+=max(0,f_v-2l)$
$fa_{u,i}$ 表示，从 $u$ ，往上的第 $2^i$ 个祖先
$dp_{u,i}$ 表示，从 $u$ 跑到 $fa_{u,i}$ ，中途可以跑子树的答案
$dp_{u,i}=dp_{u,i-1}+dp_{fa_{u,i-1},i-1}-f_{fa_{u,i-1}}$ 因为中点会被计算两次，所以要减掉
$g_u$ 表示从 $u$ 出发往祖先走，再回到 $u$ 的答案
$g_u=max(0,g_{fa_{u,0}}+dp_{u,0}-f_u-l)$

对于一个询问 $(u, v)$ ，倍增合并
先假设 $d_u>=d_v$ ，两种情况
如果 $v$ 是 $u$ 的祖先
每次往上跳 $2^k$ 步， $ans+=dp_{u,k}-f_u$

如果不是
跳到同一深度后，两个点一起往上跳，跳到 $l c a$ 的时候
$ans+=dp_{u,0}+dp_{v,0}-f_u-f_v-f_{lca}+g_{lca}$ ，只有转折点 $l c a$ 有机会往组先走

Code：

#include <bits/stdc++.h>
#define maxn 300010
#define LL long long
using namespace std;
struct Edge{
	int to, next;
	LL len;
}edge[maxn << 1];
int num, head[maxn], fa[maxn][25], n, m, d[maxn], val[maxn];
LL f[maxn], g[maxn], dp[maxn][25];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y, int z){ edge[++num] = (Edge){y, head[x], z}, head[x] = num; }

void calc(int u, int pre){
	f[u] = val[u];
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre){
			calc(v, u);
			if (f[v] - 2LL * edge[i].len > 0LL) f[u] += f[v] - 2LL * edge[i].len;
		}
	}
}

void build(int u, int pre){
	d[u] = d[pre] + 1, fa[u][0] = pre;
	for (int i = 0; fa[u][i]; ++i){
		fa[u][i + 1] = fa[fa[u][i]][i];
		dp[u][i + 1] = dp[u][i] + dp[fa[u][i]][i] - f[fa[u][i]];
	}
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre){
			dp[v][0] = f[v] + f[u] - edge[i].len;
//			printf("i : %d len : %lld %lld\n", i, edge[i].len, edge[i ^ 1].len);
			if (f[v] - 2LL * edge[i].len > 0LL) dp[v][0] -= f[v] - 2LL * edge[i].len;
//			printf("modest dp[%d][0]=%lld\n", v, dp[v][0]);
			g[v] = max(g[v], g[u] + dp[v][0] - f[v] - edge[i].len);
			build(v, u);
		}
	}
}

LL lca(int u, int v){
	int x = u, y = v;
	if (d[u] < d[v]) swap(u, v);
	LL ans = 0;
	for (int i = 20; i >= 0; --i)
		if (d[u] - (1 << i) >= d[v]){
			ans += dp[u][i] - f[u], u = fa[u][i];
		}
	if (u == v) return ans + g[u] + (d[x] > d[y] ? f[x] : f[y]);
	for (int i = 20; i >= 0; --i)
		if (fa[u][i] != fa[v][i]){
			ans += dp[u][i] + dp[v][i] - f[u] - f[v];
			u = fa[u][i], v = fa[v][i];
		}
	return ans + dp[u][0] + dp[v][0] - f[u] - f[v] - f[fa[u][0]] + g[fa[u][0]] + f[x] + f[y];
}

int main(){
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) val[i] = read();
	for (int i = 1; i < n; ++i){
		int x = read(), y = read();
		LL z = read();
		addedge(x, y, z), addedge(y, x, z);
	}
	calc(1, 0);
	build(1, 0);
/*	for (int i = 1; i <= n; ++i){
		printf("g[%d]=%d\n", i, g[i]);
		printf("f[%d]=%d\n", i, f[i]);
		printf("dp[%d][0]=%d\n", i, dp[i][0]);
		printf("dp[%d][1]=%d\n", i, dp[i][1]);
		printf("dp[%d][2]=%d\n", i, dp[i][2]);
	}*/
	while (m--){
		int x = read(), y = read();
		printf("%lld\n", lca(x, y));
	}
	return 0;
}