20pts记录

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
namespace lsq{
	typedef int lsqxx;
	struct lq{
			struct lqbz{
			    lsqxx v,nxt;
			}e[1000005];
			lsqxx h[500005],cnt;
			void add(lsqxx u,lsqxx v)
			{
				e[++cnt].v=v;e[cnt].nxt=h[u];h[u]=cnt;
			}
			#define F(z,u) for(int j=z.h[u],v=z.e[j].v;j;j=z.e[j].nxt,v=z.e[j].v)
	};
};
using namespace lsq;
lq q;
int x,y;
struct d{
	int fa,d,size;
	int bigs_xh;
	bool bigs; 
	int top;
}e[500005];
void dfs1(int t)
{
	int maxx=0,md=0;
	e[t].size=1;
	F(q,t)
	{
		if(e[v].d) continue;
		e[v].fa=t;
		e[v].d=e[t].d+1;
		dfs1(v);
		if(maxx<e[v].size)
			e[t].bigs_xh=v,
			maxx=e[v].size,
			e[v].bigs=1,
			e[md].bigs=0,
			md=e[v].size;
		e[t].size+=e[v].size;
	}
}
void dfs2(int t)
{
	if(e[t].bigs) e[t].top=e[e[t].fa].top;
	else e[t].top=t;
	F(q,t)
	{
		if(e[v].d<=e[t].d) continue;
		dfs2(v);
	}
}
int lca(int x,int y)
{
	if(e[x].top==e[y].top)
		if(e[x].d<e[y].d)
			return x;
		else
			return y;
	if(e[e[x].top].d<e[e[y].top].d)
		return lca(x,e[e[y].top].fa);
	else
		return lca(e[e[x].top].fa,y);
}
int main()
{
	cin>>n>>m>>s;
	for(int _=2;_<=n;_++)
		scanf("%d%d",&x,&y),q.add(x,y),q.add(y,x);
	e[s].d=1;
	e[s].fa=s;
	dfs1(s);
	dfs2(s);
	for(int i=1;i<=m;i++)
		scanf("%d%d",&x,&y),printf("%d\n",lca(x,y));
	return 0;
}