说句弦话，研究LCA的最好方法是......

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std; 
vector<int>E;
vector<int>G[500001];
int depth[500005];
int lo[500005],fa[500005][19];
void readin(int &x);
void addedge(int from,int to);
void dfs(int now,int fa);
int lca(int x,int y);
int main()
{
	int n,m,root;
	readin(n);readin(m);readin(root);
	lo[0]=-1;
	for(int i=1;i<=n;i++)
	 lo[i]=lo[i>>1]+1;
	for(int i=1;i<n;i++)
	{
		int ff,tt;
		readin(ff);readin(tt);
		addedge(ff,tt);
		addedge(tt,ff);
	}
	dfs(root,0);
	while(m--)
	{
		int x,y,ans;
		readin(x);readin(y);
		ans=lca(x,y);
		printf("%d\n",ans);
	}
	return 0;
}
void readin(int &x)
{
	x=0;
	char c=getchar();
	while(!isdigit(c))
	 c=getchar();
	while(isdigit(c))
	{
		x=x*10+(c-'0');
		c=getchar();
	}
	return;
}
void addedge(int from,int to)
{
	E.push_back(to);
	G[from].push_back(E.size()-1);
	return;
}
void dfs(int now,int f)
{
	depth[now]=depth[f]+1;
	int len=G[now].size();
	fa[now][0]=f;
	for(int i=1;i<=lo[depth[now]];i++)
	 fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=0;i<len;i++)
	 if(E[G[now][i]]!=f)
	  dfs(E[G[now][i]],now);
	return;
}
int lca(int x,int y)
{
	if(depth[x]<depth[y])swap(x,y);
	while(depth[x]>depth[y])//the node which is DEEPER should jump!!!
	 x=fa[x][lo[depth[y]-depth[x]]];
	if(x==y)return x;
	for(int i=lo[depth[x]];i>=0;i--)
	 if(fa[x][i]!=fa[y][i])
	  x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}