题目
参考博客 参考代码

#include<bits/stdc++.h>
using namespace std;
int const M=5e5+7;
int const N=5e5+7;
int n,m,s;
struct node{
	int a,next,len;
}e[M<<1];
int cnt,head[N];
void add(int x,int y,int len){
	e[++cnt].a =y;
	e[cnt].len =len;
	e[cnt].next =head[x];
	head[x]=cnt;
}
int lg[N]; //lg[i]表示深度为i的节点可以向上跳的次数  // 
int fa[N][37];  //fa[i][j]表示第i个节点的 2^j的祖先是谁 
int dh[N],vis[N];  //dh[i]表示i节点的深度
void dfs(int s,int fath){ //找出每个节点的深度
	fa[s][0]=fath; //fath在这一步操作比较方便 
	dh[s]=dh[fath]+1; 
	for(int i=1;i<=lg[ dh[s] ];++i){
		fa[s][i]=fa[ fa[s][i-1] ][i-1];
	}
	for(int i=head[s];i!=-1;i=e[i].next){
		if(e[i].a==fath) continue;
		dfs(e[i].a,s);
	}
}
int lca(int a,int b){
	if(dh[a]<dh[b]) swap(a,b);
	while(dh[a]>dh[b]) a=fa[a][ lg[dh[a]-dh[b]] -1 ];  //这里跳满（即跳最大值）的话，dh[a]有可能小于dh[b],所以这里lg要减一,这样循环之后，它们深度才能一样 
	if(a==b) return a;
	for(int k=lg[dh[a]];k>=0;--k){ 
		if(fa[a][k]!=fa[b][k]) a=fa[a][k],b=fa[b][k];
	} 
	return fa[a][0];
}
int main(){
	cin >> n >> m >> s;
	memset(head,-1,sizeof head);
	memset(e,-1,sizeof e);
	for(int i=1;i<=n-1;++i){
		int a,b;cin >> a >> b;
		add(a,b,1);add(b,a,1);
	}
	for(int i=1;i<=n;++i){
		lg[i]=lg[i-1]+((1<<lg[i-1])==i);   //(1<<lg[i-1])==i表示i是否是2^k次方，是就加一次   
	} 									//lg[6]=3 深度为6的点可以按二进制即倍增的方式跳3次，最大跳8(即2^3),所有点最大的那一次都是跳到0
	dfs(s,0);      //0号节点为所有节点的祖先（为了方便操作） 
	while(m--){
		int a,b;
		cin >> a >> b;
		cout << lca(a,b) << "\n";
	}
	return 0;
}