LCA最近公共祖先

最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。

暴力求解太慢，这里先摘记一种做法-倍增法。
对于每一个节点，我们先通过dfs预先处理出当前节点向根移动2的幂次方的节点编号(有种st表的感觉)。转移方程：\(fa[u][i]=fa[fa[u][i-1]][i-1],i\ge 1\)
关键数组：深度数组dep和父节点？数组fa

void dfs(int x,int f){
	dep[x]=dep[f]+1;
	fa[x][0]=f;
	for(int i=1;i<=N;++i){
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=head[x];i;i=p[i].next){
		if(p[i].to!=f) dfs(p[i].to,x);
	}
	return;
}

对于询问，首先让u与v处于同一深度，此处排除当前u和v即为最近公共祖先的情况。之后让u和v一起向根节点游，\(fa[u][i]!=fa[v][i]\)，则继续向上游。直到最后答案为\(fa[v][0]\)

int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);//使u深度大
	for(int i=N;i>=0;--i){
		if(dep[fa[u][i]]>=dep[v]){//为了处于同一深度
			u=fa[u][i];
		}
	}
	if(u==v) return v;//当前节点即为最近公共祖先
	for(int i=N;i>=0;--i){
		if(fa[u][i]!=fa[v][i]){//一起向上
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[v][0];
}

例题

模板题

洛谷 P3379 【模板】最近公共祖先（LCA）

//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*
最近公共祖先模板题
利用深搜构造lca数组
*/
const int maxm=5e5+5,inf=0x3f3f3f3f,mod=998244353,N=20;
int n,m,s,cnt=1,head[maxm],dep[maxm],fa[maxm][N+1];

struct node{
	int to,next;
}p[maxm<<1];

void add_edge(int a,int b){
	p[cnt].to=b;
	p[cnt].next=head[a];
	head[a]=cnt++;
	return ;
}

void dfs(int x,int f){
	dep[x]=dep[f]+1;
	fa[x][0]=f;
	for(int i=1;i<=N;++i){
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=head[x];i;i=p[i].next){
		if(p[i].to!=f) dfs(p[i].to,x);
	}
	return;
}

int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=N;i>=0;--i){
		if(dep[fa[u][i]]>=dep[v]){
			u=fa[u][i];
		}
	}
	if(u==v) return v;
	for(int i=N;i>=0;--i){
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[v][0];
}

void solve(){
	cin>>n>>m>>s;
	int a,b;
	for(int i=1;i<n;++i){
		cin>>a>>b;
		add_edge(a,b);
		add_edge(b,a);
	}
	dfs(s,0);
	while(m--){
		cin>>a>>b;
		cout<<lca(a,b)<<'\n';
	}
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

洛谷 P7167 [eJOI2020 Day1] Fountain

根据题意抽象为树，再利用倍增优化。具体代码与lca模板题巨像
代码：
链式前向星 qiansui_code
邻接表 qiansui_code

综合题

找树上加边所构成环的最大边权值 2023ACM暑假训练day 10 树上问题 - F
节点附加颜色条件，点点移动有限制，求移动最短时间 2023牛客多校第三场 I 难题 hrad hard hard

JZTXT

LCA

LCA最近公共祖先

例题

模板题

综合题

相关资料