https://www.luogu.com.cn/problem/P3379

#include<bits/stdc++.h>
using namespace std;

int n,m,rt;
int fa[500005][30],dep[500005],lg[500005];
vector<int> e[500005];

void dfs(int x,int fath){
	fa[x][0]=fath;
	dep[x]=dep[fath]+1;
	for(int i=1;i<=lg[dep[x]];i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(auto v:e[x]){
		if(v==fath)continue;
		dfs(v,x);
	}
}
int lca(int u,int v){
	if(dep[u]>dep[v])swap(u,v);
	while(dep[u]<dep[v])v=fa[v][lg[dep[u]-dep[v]]];
	for(int i=lg[dep[u]];i>=n;i--){
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>rt;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	dfs(rt,rt);
	for(int i=1;i<=n;i++){
		int u,v;
		cin>>u>>v;
		cout<<lca(u,v)<<endl;
	}
}