LCA求调
查看原帖
LCA求调
1063896
Mickey_miqi楼主2024/10/2 09:54
#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n, k, qu, t, d[N], dist[N], f[N][22], head[N], ver[N*2], nxt[N*2], tot;
queue<int> q;
void add(int u, int v) {
	ver[++tot] = v;
	nxt[tot] = head[u];
	head[u] = tot; 
}
void bfs() {
	q.push(1); d[1] = 1;
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (int i = head[x]; i; i = nxt[i]) {
			int y = ver[i];
			if (d[y]) continue;
			d[y] = d[x]+1;
			f[y][0] = x;
			for (int j = 1; j <= t; j++) {
				f[y][j] = f[f[y][j-1]][j-1];
			}
			q.push(y);
		}
	}
}
int lca(int x, int y) {
	if (d[x] > d[y]) swap(x, y);
	for (int i = t; i >= 0; i--) {
		if (d[f[y][i]] >= d[x]) y = f[y][i];
	}
	if (x == y) {
	    return x;
	}
	for (int i = t; i >= 0; i--) {
		if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	}
	return f[x][0];
}
void bfs1() {
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (int i = head[x]; i; i = nxt[i]) {
			int y = ver[i];
			if (dist[y] <= dist[x]+1) continue;
			dist[y] = dist[x]+1;
			q.push(y);
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &k, &qu);
	t = (log(n)/log(2))+1;
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		add(x, y);
		add(y, x);
	}
	bfs();
	memset(dist, 0x3f, sizeof(dist));
	for (int i = 1; i <= k; i++) {
		int x;
		scanf("%d", &x);
		q.push(x);
		dist[x] = 0;
	}
	bfs1();
	for (int i = 1; i <= qu; i++) {
		int x, y, z;
		scanf("%d%d", &x, &y);
		z = lca(x, y);
		cout << min(d[x]+d[y]-d[z]*2, dist[x]+dist[y]);
	}
	return 0;
}
/*
5 0 3
2 3
5 1
5 2
1 4
4 5
1 4
4 3
*/
2024/10/2 09:54
加载中...