以下是代码 倍增LCA

#include<bits/stdc++.h>
using namespace std;

const int MAXN=500000+5;
const int MAXM=500000+5;

int head[MAXN];
int father[MAXN];
bool visited[MAXM];
int bianshu;//加边用

struct edge
{
	int v,next;
}g[2*MAXM];

void addedge(int u,int v)
{
	g[++bianshu].next=head[u];
	g[bianshu].v=v;
//	g[bianshu].u=u;
	head[u]=bianshu;
	return;
}

queue <int> q;
int dep[MAXN];
void bfs(int s,int depth)
{
	q.push(s);
	dep[s]=depth;
	while(!q.empty())
	{
		int ppp=q.front();
		q.pop();
		for(int i=head[ppp];i;i=g[i].next)
		{
			if(!visited[g[i].v])
			{
				visited[g[i].v]=true;
				father[g[i].v]=ppp;
				dep[g[i].v]=dep[ppp]+1;
				q.push(g[i].v);
			}
		}
	}
}

int jump[MAXN][30];

int main()
{
//	freopen("in.in","r",stdin);
//	freopen("test.out","w",stdout);
	int n,q,s;
	int uu,vv;
	int a,b;
	int tmp;//深度差 
	scanf("%d%d%d",&n,&q,&s);
	for(int i=1;i<=n-1;++i)
	{
		scanf("%d%d",&uu,&vv);
		addedge(uu,vv);
		addedge(vv,uu);
	}
	father[s]=s;
	visited[s]=true;
	bfs(s,1);
/*	for(int i=1;i<=n;++i)
	{
		printf("father[%d]=%d\n",i,father[i]);
	}*/
	for(int i=1;i<=n;++i)
	{
		jump[i][0]=father[i];
	}
	for(int j=1;j<=25;++j)
	{
		for(int i=1;i<=n;++i)
		{
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}
	while(q--)
	{
		scanf("%d%d",&a,&b);
		
		tmp=(dep[a]>dep[b]?dep[a]-dep[b]:dep[b]-dep[a]);
		if(!tmp)
		{
			for(int k=25;k>=0;--k)
			{
				if(jump[a][k]^jump[b][k])
				{
					a=jump[a][k];
					b=jump[b][k];
				}
			}
			printf("%d\n",father[a]);
			continue;
		}
		if(dep[a]>dep[b])
		{
			for(int k=25;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					a=jump[a][k];
//					dep[a]-=(1<<k);
					tmp-=(1<<k);
				}
			} 
		}
		else
		{
			for(int k=25;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					b=jump[b][k];
//					dep[b]-=(1<<k);
					tmp-=(1<<k);
				}
			} 
		}
		if(a==b)
		{
			printf("%d\n",a);
			continue;
		}
//		printf("tmp=%d\n",tmp);
		for(int k=25;k>=0;--k)
		{
			if((jump[a][k]^jump[b][k]))
			{
				a=jump[a][k];
				b=jump[b][k];
			}
		}
		printf("%d\n",father[a]);
	}
	return 0;
}

father、dep应该都没错，求问哪里挂了