用的是重链剖分。

#include<iostream>
#include<vector> 
#include<map> 
using namespace std;
const int N=5e5+10;
vector<int>G[N],T[N];
int dep[N],fa[N],top[N],siz[N],n,m,u,v,hson,op,a,b; 
void dfs1(int x,int f){//计算每个结点子树大小 
	siz[x]=1;
	fa[x]=f;
	dep[x]=dep[f]+1;
	for(auto i:G[x]){
		if(i!=f){
			dfs1(i,x);
			siz[x]+=siz[i]; 
		}
	}
	return;
}
void dfs2(int x,int t){
	top[x]=t;
	hson=0;
	for(auto i:G[x]){
		if(i!=fa[x]&&siz[hson]<siz[i]) hson=i;
	}
	if(!hson) return;//叶子节点
	dfs2(hson,t);//在一条重链上
	for(auto i:G[x]){
		if(i!=fa[x]&&i!=hson) dfs2(i,i);//轻链 
	} 
	return;
} 
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
		else y=fa[top[y]];
	}
	return (dep[x]<dep[y]?x:y);
} 
void init(void){
	dfs1(op,op);
	dfs2(op,op);
	return;
}
int main(){
	scanf("%d%d%d",&n,&m,&op);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	init();
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
	return 0;
}
*/