P3379 【模板】最近公共祖先（LCA）
orz

#include <bits/stdc++.h> 
using namespace std;
int n,m,s;
const int maxn = 5e5 + 1;
struct edge{
	int fr,to,nxt;
}e[maxn*2] = {};
int cnt_edge = 0, head[maxn] = {};
int fa[maxn] = {}, siz[maxn] = {}, son[maxn] = {}, top[maxn] = {}, dep[maxn] = {}, dfn[maxn] = {}, rnk[maxn] = {};

void add_edge(int u, int v){
	e[++cnt_edge] = (edge){u,v,head[u]};
	head[u] = cnt_edge;
}
void dfs1(int u){
	son[u] = -1;
	siz[u] = 1;
	for(int i = head[u]; i != -1; i = e[i].nxt){
		int v = e[i].to;
		if(!dep[v]){
			dep[v] = dep[u] + 1;
			fa[v] = u;
			dfs1(v);
			siz[u] += siz[v];
			if(son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
		}
	}
}
int cnt_dfn = 0;
void dfs2(int u, int t){
	dfn[u] = ++cnt_dfn;
	rnk[cnt_dfn] = u;
	top[u] = t;
	if(son[u] == -1) return;
	dfs2(son[u],t);
	for(int i = head[u]; i != -1; i = e[i].nxt){
		int v = e[i].to;
		if(v != fa[u] && v != son[u]) dfs2(v,v);
	}
}
int lca(int u, int v){
	while(top[u] != top[v]){
		if(dep[top[u]] > dep[top[v]]){
			u = fa[top[u]];
		}else{
			v = fa[top[v]];
		}
	}
	return (dep[u] > dep[v] ? v:u);
}
int main() {
	cin>>n>>m>>s;
	for(int i = 1; i <= n; ++i) head[i] = -1;
	for(int i = 1; i <= n-1; ++i){
		int u,v;
		cin>>u>>v;
		add_edge(u,v); add_edge(v,u);
	}
	dfs1(s);
	dfs2(s,s);
	do{
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}while(--m);
	return 0;
}