RT

求大佬指点

记录详情

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

const int N = 5e5 + 3;//点数
const int M = (N-1)*2;//边数
const int K = 22;//2的最大指数

int n, q, s;
int tot;//邻接表记录边数
int first[N], nxt[M], to[M];//邻接表
int dep[N], f[N][K+1];
//dep[i]表示点i的深度  f[i][k]表示点i的第2^k次方个祖先
void add(int x, int y)//邻接表建边
{
	nxt[++tot] = first[x];
	first[x] = tot;
	to[tot] = y;
}

void _init(int x, int fa)//初始化（dfs
{
	dep[x] = dep[fa] + 1;//x比其父更深一层
	for (int i=0; i<=K-1; ++i)
		f[x][i+1] = f[f[x][i]][i];
	for (int e=first[x]; e; e=nxt[e])
	{//遍历x的出边
		int y = to[e];//出边所指的点
		if (y == fa) continue;//指向父亲就跳过
		f[y][0] = x;//那么x是y的父亲，也就是0^k号祖先
		_init(y, x);//以x为父搜索y点
	}
}

int lca(int x, int y)
{
	if (dep[x] < dep[y]) swap(x, y);//保证x更深
	for (int i=K; i>=0; --i)//将x向上跳至跟y一样深
		if (dep[f[x][i]] >= dep[y])
			x = f[x][i];
	if (x == y) return x;//如果x与y重合则y是x的祖先 也是两者的lca
	for (int i=K; f[x][i]!=f[y][i]; --i)
	{//一起往上跳至两者都是lca的儿子
		x = f[x][i];
		y = f[y][i];
	}
	return f[x][0];//父亲就是lca
}

int dis(int x, int y) {//利用lca求得两点距离
	return dep[x]+dep[y] - 2*dep[lca(x, y)];
}

int main()
{
	scanf("%d%d%d", &n, &q, &s);
	for (int i=1, x, y; i<n; ++i) {
		scanf("%d%d", &x, &y);
		add(x, y);//双向边
		add(y, x);
	}
	_init(s, 0);//以s为根初始化
	int a, b;
	while (q--)//q次询问
	{
		scanf("%d%d", &a, &b);
		printf("%d\n", dis(a, b));		
	}
	return 0;
}