求调（LCA倍增）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll an[200001][25],n,m,s,lg[200001],a,b,d[200001],k;
vector<ll>v[200001];
void dfs(ll u,ll fa){
	d[u]=d[fa]+1;
	an[u][0]=fa;
	for (ll i=1;(1<<i)<=d[u];i++) an[u][i]=an[an[u][i-1]][i-1];
	for (ll i=0;i<v[u].size();i++) if (v[u][i]!=fa) dfs(v[u][i],u);
}
ll lca(ll x,ll y){
	if (d[x]<d[y]) swap(x,y);
	while (d[x]>d[y]) x=an[x][lg[d[x]-d[y]]];
	if (x==y) return x;
	for (ll i=lg[d[x]];i>=0;i--)
	if (an[x][i]!=an[y][i]){
		x=an[x][i];
		y=an[y][i];
	}
	return an[x][0];
}
int main(){
	cin>>n>>m>>s;
	for (ll i=1;i<n;i++){
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	lg[0]=-1;
	for (ll i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
	dfs(s,0);
	while (m--){
		cin>>a>>b;
		cout<<lca(a,b)<<'\n';
	}
}