#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500001;
int n,m,f[N][20],dep[N];
bool vis[N];
int head[N],cnt=0,s;
struct node{
	int to,nxt;
}e[N];
void add(int u,int v){
	cnt++;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void dfs(int x){
	for(int i=1;(1<<i)<dep[x];i++){
		f[x][i]=f[f[x][i-1]][i-1]; 
	}
	for(int i=head[x];i;i=e[i].nxt){
		if(vis[e[i].to])continue;
		vis[e[i].to]=true;
		dep[e[i].to]=dep[x]+1;
		f[e[i].to][0]=x;
		dfs(e[i].to);
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	int lg=log2(dep[u]-dep[v]);
	for(int i=lg;i>=0;i--){
		if(dep[f[u][i]]>=dep[v])u=f[u][i];
	}
	if(u==v)return u;
	lg=log2(dep[u]);
	for(int i=lg;i>=0;i--){
		if(f[u][i]==f[v][i])continue;
		u=f[u][i];
		v=f[v][i];
	}
	return f[u][0];
}
signed main(){
	scanf("%lld %lld %lld",&n,&m,&s);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%lld %lld",&u,&v);
		add(u,v);
		add(v,u);
	}
	dep[s]=1;
	vis[s]=true;
	dfs(s);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%lld %lld",&u,&v);
		printf("%lld\n",lca(u,v));
	}
	return 0;
}

评测记录

怎么调都没用QWQ