自动搬运

查看原文

来自洛谷，原作者为

	kouki_hash ‏‎

搬运于2025-08-24 22:46:44，当前版本为作者最后更新于2025-03-20 20:41:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

最近正在学 LCA，正好看到蓝桥杯省赛这题，似乎刚放上去还没有题解，正好作为本蒟蒻第一篇题解练练手结果发现不会写题解。

题意分析

题意比较简单，在一棵有 $N$ 个点的无向有权树上选出 $K$ 个点，随后有 $K$ 个询问，每次询问会跳过一个点，跳过的点从1、2、3依次到 $K$，求每次依次访问剩余点的路径权值和最小值。

解题思路

首先很容易得出：由于访问顺序固定，任意连续访问点之间的路径权值和都要最小，这样按顺序访问所有点后的路径权值和一定最小。而一棵无向树上任意两点的最短路径有且只有一条，并且经过这两点的 LCA 即最近公共祖先（不管边带不带权都一样）。这样的最短路径很好求得，用树上前缀和 sum[i] 表示树根到结点i的路径权值和，那么任意两点 a 和 b 的最短路径为

$$dis(a,b)=sum[a]+sum[b]-2 \times \operatorname{LCA}(a,b) $$

再求出按原访问顺序的路径权值前缀和，对于 $A _ {i}$ 有

$$ans[i]=dis(A _ {1},A _ {2})+dis(A _ {2},A _ {3})+\dots+dis(A _ {i-1},A _ {i})(2 \le i \le K) $$

那么当跳过 $A _ {i}$ 时，答案就是

$$\begin{cases} ans[K]-ans[2] & i = 1 \\ ans[i-1]+dis(a[i-1],a[i+1])+ans[K]-ans[i+1] & 2 \le i \le K-1 \\ ans[K-1] & i = K \end{cases} $$

那么问题来到如何求出一些给定点对的 LCA。这里本蒟蒻用了离线算法 Tarjan 算法，因为懒得写倍增因为赛时可以比较快捷地实现。

简单来说，此题需要以下步骤：读入树后，进行一次 DFS 预处理出所有结点的树上前缀和 sum[i]。读入游览线路，记录下相邻数对和间隔数对。跑一遍 Tarjan 算法，求出按照原访问顺序的路径权值前缀和，求出答案。时间复杂度为 $O\left(m\,\alpha(m+n, n) + n\right)$。

具体代码

#include <bits/stdc++.h>
using namespace std;

long long a[100005];

bool vis1[100005];
long long sum[100005];

bool vis2[100005];
long long fa[100005];
vector<long long>q[100005];//保存要查询的点对，离线查询

map<pair<long long, long long>, long long>ma;//保存点对及其LCA

long long ans[100005];

struct node {
	long long v;
	long long t;
} edge;

vector<struct node>g[100005];

long long find(long long x) {
	if (fa[x] == x) {
		return x;
	} else {
		return fa[x] = find(fa[x]);
	}
}

void dfs(long long x) {//预处理求出树上前缀和
	vis1[x] = true;

	for (long long i = 0; i < g[x].size(); i++) {
		if (vis1[g[x][i].v] != true) {
			sum[g[x][i].v] = g[x][i].t + sum[x];
			dfs(g[x][i].v);
		}
	}
	return;
}

void tarjan(long long x) {//标准tarjan模板
	vis2[x] = true;

	for (long long i = 0; i < g[x].size(); i++) {
		if (vis2[g[x][i].v] == false) {
			tarjan(g[x][i].v);
			fa[g[x][i].v] = x;
		}
	}

	for (long long i = 0; i < q[x].size(); i++) {
		if (vis2[q[x][i]] == true) {
			ma[ {x, q[x][i]}] = find(q[x][i]);
			ma[ {q[x][i], x}] = find(q[x][i]);
		}
	}
	return;
}

long long get_dis(long long x, long long y) {//求出树上两点最短路径
	return sum[x] + sum[y] - 2 * sum[ma[ {x, y}]];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	long long n, k;
	cin >> n >> k;

	for (long long i = 1; i < n; i++) {
		long long u, v, t;
		cin >> u >> v >> t;

		g[u].push_back({v, t});
		g[v].push_back({u, t});
	}

	dfs(1);//预处理出树上前缀和

	for (long long i = 1; i <= k; i++) {//离线保存所需查询
		cin >> a[i];
		if (i >= 2) {//相邻点对
			q[a[i]].push_back(a[i - 1]);
			q[a[i - 1]].push_back(a[i]);
		}
		if (i >= 3) {//间隔点对
			q[a[i]].push_back(a[i - 2]);
			q[a[i - 2]].push_back(a[i]);
		}
	}

	for (long long i = 1; i <= n; i++) {//tarjan算法初始化
		fa[i] = i;
	}

	tarjan(1);//预处理出所求LCA

	for (long long i = 2; i <= k; i++) {//按原访问顺序的路径权值前缀和
		ans[i] = ans[i - 1] + get_dis(a[i], a[i - 1]);
	}

	for (long long i = 1; i <= k; i++) {//分段得出答案
		if (i == 1) {
			cout << ans[k] - ans[2] << " ";
		} else if (i == k) {
			cout << ans[k - 1] << " ";
		} else {
			cout << ans[i - 1] + get_dis(a[i - 1], a[i + 1]) + ans[k] - ans[i + 1] << " ";
		}
	}
	return 0;
}

提交，AC，然后这篇题解就结束了果然写题解好难。