在某OJ上拿了70分，TLE三个点，然鹅洛谷数据测，输出全部为0……

#include<iostream>//lca
#include<cmath>
#include<algorithm>
#define maxx 500000+1
using namespace std;
int n,m,s,ans;
int dep[maxx],fa[maxx][22],endd[maxx],nextt[maxx],last[maxx];
int lg[maxx];
void dfs(int x)//预处理fa数组 
{
	dep[x]=dep[fa[x][0]] + 1;
	int k = lg[dep[x]];
	for(int i = 1;i <= k;i ++) fa[x][i]=fa[fa[x][i-1]][i-1];
	int y=last[x];
	while(y)
	{
		if(endd[y] != x) dfs(endd[y]);
		y=nextt[y];//遍历y的所有儿子
	}
}

int lca(int u,int v)
{
	if(dep[u] < dep[v]) swap(u,v);
	int k = dep[u] - dep[v];
	int s = lg[n];
	for(int i = 0 ; i <= s ; i ++)	
		if(k & (1 << i)) u = fa[u][i];
	if(u == v) return u;
	s = lg[n];
	for(int i = s ; i >= 0 ; i --)
	{
		if(fa[u][i] != fa[v][i]) u=fa[u][i],v=fa[v][i];
	}
	return fa[u][0];
}
	
int main()
{
	cin>>n>>m>>s;
	int x,y;
	for(int i=1;i<n;i++)
	{
		cin>>x>>y;
		fa[y][0]=x;
		endd[i]=y;
		nextt[i]=last[x];
		last[x]=i;
	}
	
	for(int i = 1 ; i <= n ; i ++)//求对数 
		lg[i] = lg[i-1] + (1 << lg[i-1] == i);
	
	/*for(int i=1;i <= n;i ++)
		if(fa[i][0] == 0)
		{
			dfs(i);
			break;
		}*/
	dfs(s);
	int a,b;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		cout<<lca(a,b)<<endl;
	}
		
		
		
	return 0;
}