自动搬运

查看原文

来自洛谷，原作者为

	y_kx_b 清新题目今何在 ～ Lunatic Probrems Everywhere

搬运于2025-08-24 22:48:19，当前版本为作者最后更新于2023-05-12 16:08:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

rStage5 - Hard Conveyors

预计难度：*2100 左右，绿~蓝。

前置芝士：lca，树剖（其实也可以不用）。

设 $dis_u$ 为离 $u$ 点最近的一个关键点与它的距离，显然可以使用 dijkstra 等算法 $O(n\log n)$ 求出（以堆优化 dijkstra 为例：将所有关键节点的 $dis$ 设为 $0$ 并全部加入优先队列，然后跑正常的堆优化 dijkstra 即可）。

（upd：好像可以 dfs 就能预处理出这个 $dis$ 数组，但是好像挺麻烦，没试过。）

因为每条路径显然形如 $s\to x\to \operatorname{key}(x)\to x\to t$，其中 $x$ 是 $s\to t$ 路径上的点（可以取到端点），$\operatorname{key}(x)$ 是离 $x$ 最近的关键点。那么预处理出 $dis$ 数组，对于每次询问 $O(n)$ 枚举 $s\to t$ 上的 $x$ 统计这种情况下的最小路径长度，总复杂度 $O(n\log n+qn)$。

发现枚举 $x$ 实际上只是为了求 $dis_x$ 的最小值（因为 $s\to x$ 加上 $x\to t$ 的长度一定等于 $s\to t$）。于是直接套个树剖求一条路径上的 $dis$ 最小值即可，复杂度 $O(n\log n+q\log n)$。

upd：好像倍增求 lca 也可以维护一条路径上的最小值 qwq：设 $st_{i,j}$ 为 $i$ 到根的链中底部 $2^j$ 个点的 $dis$ 最小值（即集合 $\complement_{i\to fa_{i,j}}\{fa_{i,j}\}$ 内 $dis$ 的最小值，其中 $fa_{i,j}$ 表示 $i$ 点的 $2^j$ 级祖先，$u\to v$ 表示 $u$ 到 $v$ 的最短路径上的点构成的集合）。那么求 lca 时 $u,v$ 两个点往上跳的同时用 $st$ 数组更新 $dis$ 最小值就行了。This sol code。

code：

int n, q, k;
int head[N], ne[N << 1], to[N << 1], w[N << 1], idx1 = 0;
void add(int u, int v, int x) {
	to[idx1] = v, w[idx1] = x, ne[idx1] = head[u], head[u] = idx1++;
}
int dis[N];
bool dijvis[N];
void dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	memset(dijvis, 0, sizeof dijvis);
	priority_queue<pii, vector<pii>, greater<pii>> Q;
	while(k--) {
		int x = read();
		Q.em(dis[x] = 0, x);
	}
	while(!Q.empty()) {
		int u = Q.top().y; Q.pop();
		if(dijvis[u]) continue;
		dijvis[u] = 1;
		for(int i = head[u]; ~i; i = ne[i]) {
			int &v = to[i];
			if(dis[v] > dis[u] + w[i])
				dis[v] = dis[u] + w[i], Q.em(dis[v], v);
		}
	}
}
#define ws ambiguous1
int ws[N];
int siz[N], fa[N], son[N], dph[N], top[N], dfn[N], rnk[N];
void dfs1(int u, int f) {
	dph[u] = dph[f] + 1, fa[u] = f, siz[u] = 1;
	for(int i = head[u]; ~i; i = ne[i]) if(to[i] != f) {
		int &v = to[i];
		ws[v] = ws[u] + w[i];
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]]) son[u] = v;
	}
}
int timer = 0;
void dfs2(int u, int tp) {
	top[u] = tp, dfn[u] = ++timer, rnk[timer] = u;
	if(son[u]) dfs2(son[u], tp);
	for(int i = head[u]; ~i; i = ne[i]) if(to[i] != fa[u] && to[i] != son[u]) {
		int &v = to[i];
		dfs2(v, v);
	}
}
int st[20][N];
int minimum(int l, int r) {
	if(l > r) return 0x3f3f3f3f;
	int k_ = __lg(r - l + 1);
	return min(st[k_][l], st[k_][r - (1 << /*k*/k_) + 1]);
}
int get_ans(int u, int v) {
	int res = 0x3f3f3f3f, tmp = ws[u] + ws[v];
	while(top[u] != top[v]) {
		if(dph[top[u]] < dph[top[v]]) swap(u, v);
		res = min(res, minimum(dfn[top[u]], dfn[u]));
		u = fa[top[u]];
	}
	if(dph[u] > dph[v]) swap(u, v);
	res = min(res, minimum(dfn[u], dfn[v]));
	return tmp - (ws[u] << 1) + (res << 1);
    //tmp - ws[lca] * 2 = u->v 路径长度
}
bool major(int Testcase = 1) {
	memset(head, -1, sizeof head);
	n = read(), q = read(), k = read();
	for(int i = 1; i < n; i++) {
		int u = read(), v = read(), ww = read();
		add(u, v, ww), add(v, u, ww);
	}
	dijkstra();
	dfs1(1, 0);
	dfs2(1, 0);
	memset(st, 0x3f, sizeof st);
	for(int i = 1; i <= n; i++) st[0][i] = dis[rnk[i]];
	for(int j = 1; j < 20; j++) for(int i = 1; i <= n; i++)
		if(i + (1 << j) - 1 <= n)
			st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
	while(q--) {
		int s = read(), t = read();
		printf("%d\n", get_ans(s, t));
	}
	return Testcase;
}