思路：N-1条边的无向图，DFS时b[x]记录x点是树的第几层，c[x]记录x点的祖先节点中最近的有分支节点，d[x]记录x点的父节点。如果x和y在c中数据不同，证明他俩相遇前要经过有分支的结点，直接跳过去。当x与y最近的有分支节点相同后x和y谁的层数大谁向上（防止x是y的祖先或者y是x的祖先），直到相遇 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],d[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;
			d[a[i].to]=k;
			if(a[a[h[k]].next].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(c[x]!=c[y])
			{
				if(b[x]<b[y])
					y=c[y];
				else
				if(c[x]!=c[y])
					x=c[x];
			}
			else
			{
				if(b[x]<b[y])
					y=d[y];
				else
				if(b[x]>b[y])
					x=d[x];
				else
				if(x!=y)
					x=d[x];
			}
		}
		printf("%d\n",x);
	}
	return 0;
}