景区导游（tarjan算法求LCA）

解题思路:

思路详解见：https://www.acwing.com/solution/content/239076/

参考代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int, int> pii;
const int N = 1e5 + 10, M = 2 * N;
int e[M], ne[M], h[N], w[M], idx;
int p[N], st[N];
long long dist[N];
long long res[M];
int road[N];
int n, k;
vector<pii> query[N];

void add(int a, int b,int c) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int find(int x) {
	if (p[x] != x)
		p[x] = find(p[x]);
	return p[x];
}

void dfs(int u, int fat) {
	for (int i = h[u]; i != -1; i=ne[i]) {
		int j = e[i];
		if (j != fat) {
			dist[j] = dist[u] + w[i];
			dfs(j, u);
		}
	}
}

void tarjan(int u) {
	st[u] = 1;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		if (!st[j]) {
			tarjan(j);
			p[j] = u;
		}
	}

	for (auto item : query[u]) {
		int y = item.first, id = item.second;
		if (st[y] == 2) {
			int anc = find(y);
			res[id] = dist[u] + dist[y] - dist[anc] * 2;
		}
	}
	st[u] = 2;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	int t = n - 1;
	memset(h, -1, sizeof h);
	while (t--) {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
	}
	for (int i = 0; i < k; i++)
		cin >> road[i];
	int ct = 0;
	// 初始化距离
	dfs(1, -1);
	// 初始化并查集
	for (int i = 1; i <= n; i++)
		p[i] = i;
	// 初始化查询
	for (int i = 0, ct = 1; i < k; i++) {
		// 下一个点
		query[road[i]].push_back({ road[i + 1],ct });
		query[road[i + 1]].push_back({ road[i],ct });
		ct++;
		// 下下个点
		query[road[i]].push_back({ road[i + 2],ct });
		query[road[i + 2]].push_back({ road[i],ct });
		ct++;
	}
	tarjan(1);
	long long ans = 0;
	// 总距离
	for (int i = 1; i <= k; i++) {
		ans += res[2 * i - 1];
	}
	// 删去第一个点
	cout << ans - res[1] << ' ';
	// 删去中间点
	for (int i = 2; i < k; i++) {
		cout << ans - res[2 * (i - 1) - 1] - res[2 * i - 1] + res[2 * (i - 1)] << ' ';
	}
	// 删去最后一个点
	cout << ans - res[2 * k - 3];
	return 0;
}