Rt

普通的倍增LCA 不知道哪里打崩了（码风奇丑勿怪）

#include<queue>
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
vector<int> g[500012];
int n,m,s,maxk=20;
int fa[500012][20];
int h[500012];
bool vis[500012];
void ini(){
	for(int i=1;i<=maxk;i++){
		for(int j=1;j<=n;j++){
			fa[j][i]=fa[fa[j][i-1]][i-1];
		}
	}
	return ;
} 
void bfs(){
	queue<int> q;
	q.push(s);
	vis[s]=true;
	h[s]=0;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		for(int i=0;i<g[k].size();i++){
			if(!vis[g[k][i]]){
				fa[g[k][i]][0]=k;
				h[g[k][i]]=h[k]+1;
				vis[g[k][i]]=true;
				q.push(g[k][i]);
			}
		}
	}
	return ;
}
int LCA(int a,int b){
	if(a==b)return a;
	if(h[a]<h[b])swap(a,b);
	int k=h[a]-h[b];
	for(int i=0;i<=maxk;i++){
		int q=(1<<i);
		if(q&k) a=fa[a][i];
	}
	if(a==b)return b;
	for(int i=maxk;i>=0;i--){
		if(fa[a][i]!=fa[b][i]){
			a=fa[a][i];
			b=fa[b][i];
		}
	}
	return fa[b][0];
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n-1;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	fa[s][0]=-1;
	bfs();
	ini();
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",LCA(x,y));
	}
	return 0;
}

求dalao帮忙看看/kk