文章

lca模板

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=5e5+10;
int n,m,s,tot;
struct zzz{
	int t,nex;
}e[500010 << 1];
int head[500010];
int depth[500010];
int fa[500010][22];
int lg[500010];
void add(int u,int v){
	tot++;
	e[tot].t=v;
	e[tot].nex=head[u];
	head[u]=tot;
	return ;
}
void dfs(int now,int fath){
	fa[now][0]=fath;
	depth[now]=depth[fath]+1;
	for(int i=1;i<lg[depth[now]];i++){
		fa[now][i]=fa[fa[now][i-1]][i-1]; 
	}
	for(int i=head[now];i;i=e[i].nex){
		if(e[i].t!=fath){//确定是往下走 
			dfs(e[i].t,now);
		}
	}
	return ;
}
int lca(int u,int v){
	if(depth[u]<depth[v]){
		swap(u,v);
	}
	while(depth[u]>depth[v]){
		u=fa[u][lg[depth[u]-depth[v]]-1];
	}
	if(u==v) return u;
	for(int k=lg[depth[u]]-1;k>=0;k--){
		if(fa[u][k]!=fa[v][k]){
			u=fa[u][k];
			v=fa[v][k];
		}
	}
	return fa[u][0];
} 
int main()
{
	int u,v,i;
	cin>>n>>m>>s;//结点个数 询问个数 根节点 
	for(i=1;i<=n-1;i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(i=1;i<=n;i++){
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	}
	dfs(s,0);//根节点的父亲结点定义为0 
	for(i=1;i<=m;i++){
		cin>>u>>v;
		cout<<lca(u,v)<<endl;
	}
	return 0;
}
License:  CC BY 4.0