link

Code：

#include<bits/stdc++.h>
using namespace std;
const int N=6e5;
vector<int> g[N];
int depth[N],fa[N];
int size[N],son[N],top[N];

void dfs1(int u,int f)
{
	fa[u]=f,size[u]=1;
	depth[u]=depth[f]+1;
	for (int v:g[u])
		if (v!=f) {
			dfs1(v,u);
			if (size[v]>size[son[u]]) son[u]=v;
		}
}
void dfs2(int u,int topf)
{
	top[u]=topf;
	if (son[u]) dfs2(son[u],topf);
	for (int v:g[u])
		if (!top[v])
			dfs2(v,v);
}
int LCA(int x,int y)
{
	while (top[x]!=top[y]) {
		if (depth[top[x]]<depth[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	return depth[x]<depth[y]?x:y;
}
int main()
{
	int n,m,s,x,y;
	scanf("%d%d%d",&n,&m,&s);
	for (int i=1;i<n;i++) {
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	} dfs1(s,0),dfs2(s,s);
	while (m--) {
		scanf("%d%d",&x,&y);
		printf("%d\n",LCA(x,y));
	}
	return 0;
}