时间戳

首页 > 技术文章 > 【总结】lca最近公共祖先

【总结】lca最近公共祖先

huixinxinw 2020-02-04 18:11 原文

一.定义：

给出有根树T中的两个不同的节点u和v，找到一个离根最远的节点x，使得x同时是u和v的祖先，x就是u和v的最近公共祖先(Lowest common ancestor)

二.暴力算法

先从u往根节点遍历，经过的点都打一个标记

再从v往根节点遍历，路上碰到的第一个打标记的点就是它们的LCA.

时间复杂度：一次询问是O(n)的，n为树的节点个数。

三.倍增算法

我们记fa[u]为u的父节点，即从u向根走1步能到达的节点，对根节点我们记fa[root] = 0.

记up[u] [k]为从u向根走2k步到达的节点。

显然有

up[u] [0] = fa[u]

up[u] [k] = up[up[u] [k – 1]] [k – 1]

具体实现

那么，有了up[u] [k]数组之后我们怎么求LCA呢？

若u和v的深度不同，则通过up数组先把他们调整到同一深度

我们从大到小枚举k，比较up[u] [k]与up[v] [k]

若up[u] [k] == up[v] [k]

说明up[u] [k]是u和v的公共祖先

若up[u] [k] != up[v] [k]

说明u和v还没有走过LCA

令u = up[u] [k], v = up[u] [k]

可以证明，最后u和v的父亲就是所求的LCA.

代码

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int read(){
	int f=0,a=0;char p=getchar();
	while(!isdigit(p)){f|=p=='-';p=getchar();}
	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
	return f?-a:a; 
}
vector<int> m[500005];
int f[500005][21],dep[500005];
int tot;
int next[500005*2],first[500005*2],go[500005*2];
void firs(int u,int fa){
	dep[u]=dep[fa]+1;//该节点的深度 等于其父亲节点加一
	f[u][0]=fa;
	for(int i=0;i<=19;i++)f[u][i+1]=f[f[u][i]][i];
	for(int e=first[u];e;e=next[e]){
		int v=go[e];
		if(v==fa)continue;
		firs(v,u);
	}
}
inline int lca(int x,int y){//求x和y的最近公共祖先 
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--){
		if(dep[f[x][i]]>=dep[y])x=f[x][i];//让x和y到一个深度 
		if(x==y)return x;
	}
	for(int i=20;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	} 
	return f[x][0];
}
void Add(int u,int v){
	 next[++tot]=first[u];first[u]=tot;go[tot]=v;
	 next[++tot]=first[v];first[v]=tot;go[tot]=u;
}
int main(){
	int n,M,s;//n个节点 m个询问 s是根节点
	int x,y;
	n=read();M=read();s=read(); 
	for(int i=1;i<=n-1;i++){
		x=read();y=read();	
		Add(x,y);
	}  
	firs(s,0);
//	for(int i=1;i<=20;i++){
//		for(int j=1;j<=n;j++)cout<<f[j][i]<<" ";
//	}
	for(int i=1;i<=M;i++){
		x=read();y=read();
		cout<<lca(x,y)<<endl;
	}
	return 0;
}

至于例题的话写过一些了有时间再整理(趴。

推荐阅读