戳这里

题目传送门

代码：

//LCA最近公共祖先模板
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+7,M=20;
struct node{
	int to,next;
}e[N*2];
int n,m,s,u,v;
int head[N],cnt,rt;
void addedge(int u,int v){
	e[++cnt].next=head[u];
	head[u]=cnt;
	e[cnt].to=v;
}//加边 
int dep[N],far[N][21];
void dfs(int u,int fa,int depth){//当前，父亲，深度 
	dep[u]=depth;
	far[u][0]=fa;//距离2^0次方祖先编号就是父亲编号
	for(int i=1;i<=20;i++)//注意从1开始  
		far[u][i]=far[far[u][i-1]][i-1];//2^i=2^i-1+2^i-1
	
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v==fa) continue;//如果下一层要走的节点是父亲，跳过 
		dfs(v,u,depth+1);
	}//遍历 
}
int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=M;i>=0;i--)
		if(dep[far[u][i]]>=dep[v]){//如果u向上跳2^i次方层还是比v低 
			u=far[u][i];//u向上跳到u同一层 
			if(u==v) return u;//如果u跳到祖先后与v相同，则u就是答案 
		}//倍增思想 
	for(int i=M;i>=0;i--){//此时u、v已经在同一层 
		if(far[u][i]!=far[v][i]){
			u=far[u][i];
			v=far[v][i];
		}
	}//一起向上跳，跳到父节点相同时停止 
	return far[u][0];//返回祖先 
}
int main(){
	cin>>n>>m>>s; 
	for(int i=1;i<n;i++){
		cin>>u>>v;
		addedge(u,v);
		addedge(v,u);
	}
	dfs(s,0,1);
	while(m--){
		cin>>u>>v;
		if(u==v) cout<<far[u][0];
		else cout<<lca(u,v)<<endl;
	}
	return 0;
}

球球大佬们 蒟蒻不才