https://www.luogu.com.cn/record/172659191

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

int n,m,ss;
vector<int>d[500005];
bool p[500005];
int dp[500005][21];
int a[500005];
int po[21];
int lg[500005];

void dfs(int s) {
	for (int i=0; i<d[s].size(); i++) {
		int g=d[s][i];
		if (p[g]) continue;
		dp[g][0]=s,a[g]=a[s]+1,p[g]=1;
		dfs(g);
	}
	return;
}

void bz() {
	po[0]=1;
	for (int i=1; i<=20; i++) {
		po[i]=po[i-1]*2;
		for (int k=1; k<=n; k++) {
			if (po[i]>=a[k])continue;
			dp[k][i]=dp[dp[k][i-1]][i-1];
		}
	}
	for (int i=0,o=0; i<=n; i++) {
		lg[i]=o;
		if (i==po[o]) o++;
	}
	return;
}

void lca(int x,int y) {
	if (a[x]<a[y]) swap(x,y);
	while (a[x]>a[y]) {
		int o=lg[a[x]-a[y]];
		x=dp[x][o];
	}
	if (x==y) {
		printf("%d\n",x);
		return;
	}
	for (int i=lg[a[x]-1]; i>=0; i--) {
		if (dp[x][i]!=dp[y][i])
			x=dp[x][i],y=dp[y][i];
	}
	printf("%d\n",dp[x][0]);
	return;
}

int main() {

	scanf("%d%d%d",&n,&m,&ss);
	for (int i=1; i<n; i++) {
		int x,y;
		scanf("%d%d",&x,&y);
		d[x].push_back(y);
		d[y].push_back(x);
	}
	
	dp[ss][0]=ss,p[ss]=1,a[ss]=1;
	dfs(ss);
	bz();
	
	while (m--) {
		int x,y;
		scanf("%d%d",&x,&y);
		lca(x,y);
	}
	return 0;
}