思路：N-1条边的无向图，DFS时b[x]记录x点是树的第几层，c[x]记录x点的父节点是谁。然后x和y谁的层数大谁向上，直到相遇 100分1，2到13，14号测试点TLE，求调

#include<bits/stdc++.h>
using namespace std;
struct st
{
	int from,to,next;
}a[1000001];
int h[500001],cnt=1,b[500001],c[500001];
void add(int u,int v)
{
	a[cnt].from=u;
	a[cnt].to=v;
	a[cnt].next=h[u];
	h[u]=cnt;
	cnt++;
}
void dfs(int k,int t)
{
	int i;
	for(i=h[k];i;i=a[i].next)
	{
		if(b[a[i].to]==0)
		{
			b[a[i].to]=t;
			if(a[h[k]].next)
				c[a[i].to]=k;
			else
				c[a[i].to]=c[k];
			dfs(a[i].to,t+1);
		}
	}
}
int main() 
{
	int n,m,s,i,u,v,x,y;
	scanf("%d%d%d",&n,&m,&s);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	b[s]=1;
	c[s]=s;
	dfs(s,2);
	for(i=0;i<m;i++)
	{
		scanf("%d%d",&x,&y);
		while(x!=y)
		{
			if(b[x]<b[y])
				y=c[y];
			else
			if(b[x]>b[y])
				x=c[x];
			else
			if(x!=y)
				x=c[x];
		}
		printf("%d\n",x);
	}
	return 0;
}