RT. 倍增LCA。

#include<iostream>
using namespace std;
struct edge{
	int u,v,nxt;
}a[1000010];
int f[500010][23],dep[500010],edgegs,head[500010];
int addln(int u,int v){
	a[++edgegs].u=u;
	a[edgegs].v=v;
	a[edgegs].nxt=head[u];
	head[u]=edgegs;
}
struct rtr{
	rtr(int a,int b){
		point=b;leng=a;
	}
	int point ,leng;
};
int log_2[1000010];
int rc(int fa,int now){
	f[now][0]=fa;dep[now]=dep[fa]+1;
	for(int i=1;i<=log_2[dep[now]];i++)f[now][i]=f[f[now][i-1]][i-1];
	for(int i=head[now];i;i=a[i].nxt)
			if(a[i].v!=fa)rc(now,a[i].v);
}
rtr lca(int l,int r){
	if(dep[r]<dep[l])swap(l,r);
	int ans=dep[r]-dep[l];
	while(dep[r]>dep[l])r=f[r][log_2[dep[r]-dep[l]]-1];
	if(l==r)return rtr(ans,l);
	for(int i=log_2[dep[l]]-1;i>=0;i--){
		if(f[l][i]!=f[r][i]){
			l=f[l][i];
			r=f[r][i];
			ans+=i*2;
		}
	}
	return rtr(ans,f[r][0]);
}
int main(){
	int n,m,s;
	cin>>n>>m>>s;
	int u,v;
	for(int i=1;i<n;i++)
		log_2[i]=log_2[i-1]+(1<<log_2[i-1]==i);
	for(int i=1;i<n;i++){
		cin>>u>>v;
		addln(u,v);
		addln(v,u);
	}
	rc(0,s);
	for(int i=0;i<m;i++){
		cin>>u>>v;
		cout<<lca(u,v).point<<endl;
	}
	return 0;
}

附上#1数据： input:

10 10 8
10 9
3 1
8 2
3 8
7 3
5 9
8 5
8 6
4 6
8 4
6 1
7 1
10 1
6 1
9 1
4 1
7 1
10 1
10 1

output:``` 8 8 3 8 8 8 8 8 8 8