小可初学“树连刨分”，见旧人曰LCA，大喜，遂入，已而完，红紫交加，不信，复交几方，皆大败而归，闻luoguo有一宝地，故求调QMQ link

link

#include<bits/stdc++.h>
using namespace std;
const int M=5e5+1;
int read(){
	int sum=0,k=1;char c=getchar();
	while(c<'0'&&c>'9'){
		if(c=='-')k=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		sum=sum*10+c-'0';
		c=getchar();
	}
	return sum*k;
}
struct Node{
	int next,to;
}e[M];
int head[M],k=0;
void adde(int u,int v){
	k++;
	e[k].next=head[u];
	e[k].to=v;
	head[u]=k;
}
int Tree_Size[M];
int Tree_Son[M];
int fa[M];
int Deep[M];
void Build_Dfs(int u,int ft){
	Tree_Size[u]=1;
	Deep[u]=Deep[ft]+1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v==ft) continue;
		fa[v]=u;
		Build_Dfs(v,u);
		Tree_Size[u]+=Tree_Size[v];
		if(Tree_Size[Tree_Son[u]]<Tree_Size[v]){
			Tree_Son[u]=v;
		}
	}
}
int toop[M];
void Find_Root_Dfs(int u,int Top){
	toop[u]=Top;
	if(Tree_Son[u]==0) return ;
	Find_Root_Dfs(Tree_Son[u],Top);
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v==Tree_Son[u]) continue;
		if(v==fa[u]) continue;
		Find_Root_Dfs(v,v);
	}
}
int LCA(int a,int b){
	while(toop[a]!=toop[b]){
		if(Deep[toop[a]]<Deep[toop[b]])
			swap(a,b);
		a=fa[toop[a]];
	}
	if(Deep[a]<Deep[b]) return a;
	else return b;
}
signed main(){
	
	int n=read(),m=read(),s=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		adde(u,v);
		adde(v,u);
	}
	Build_Dfs(s,0);
	Find_Root_Dfs(s,s);
	while(m--){
		int a=read(),b=read();
		cout<<LCA(a,b)<<endl;
	}
	return 0;
}