首页 > 代码库 > 最近公共祖先（lca）

最近公共祖先（lca）

2024-07-18 20:35:22   211人阅读

囧啊囧。

lca的求法太多了

倍增，tarjan，st，lct，hld....

后边三个我就不写了，其中st我没写过，估计用不上，在线用倍增，离线用tarjan就行了。

嗯。

第一种，倍增（nlogn，在线）：

倍增的思想用在树上，即可以求出lca。

我们维护二维数组，f[i][j]，表示i号点的第2^j号祖先，显然2^0=1也就是f[i][0]就是他的父亲

我们需要用dfs维护一个深度数组（求lca需要用）

还需要倍增求出所有的f[i][j]，学过st的都应该知道，在这里f[i][j]=f[ f[i][j-1] ][j]

然后是我们的求lca了，很简单，首先要将这两个点u和v调到同一深度，这样以后操作都是同深度的。

怎么调深度呢？很简单，将他们的深度相减，我们设为dep，那么这个dep的就对应了深一点的那个点需要上升的高度，恩，应该马上能想到，直接用二进制表示深度然后一直爬上去就行了，这就是倍增的思想，log级别

同一深度时，我们要同时上升啦～我们继续用倍增思想，依次上升2^k的高度。什么时候上升呢？当然是f[u][k]!=f[v][k]的时候，因为这说明他们的祖先还不同，他们位于2棵子树，所以要上升。并且顺序要从大到小！否则求不到最小的祖先，很容易理解的。

代码很简单，12行

#include <iostream>#include <cstdio>using namespace std;#define dbg(x) cout << #x << " = " << x << endl#define read(x) x=getint()#define rdm(u) for(int i=ihead[u]; i; i=e[i].next)const int N=10000, M=15;inline const int getint() { char c=getchar(); int k=1, ret=0; for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) ret=ret*10+c-‘0‘; return k*ret; }struct ed { int to, next; } e[N<<1];int cnt, ihead[N], n, m, dep[N], fa[N][M];bool vis[N];inline void add(const int &u, const int &v) {	e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v;	e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u;}void dfs(const int &u, const int &d) {	vis[u]=1; dep[u]=d;	rdm(u) if(!vis[e[i].to]) { dfs(e[i].to, d+1); fa[e[i].to][0]=u; }}inline void bz() { for(int j=1; j<M; ++j) for(int i=1; i<=n; ++i) fa[i][j]=fa[fa[i][j-1]][j-1]; }inline int lca(int u, int v) {	if(dep[u]<dep[v]) swap(u, v);	int d=dep[u]-dep[v];	for(int i=M-1; i>=0; --i) if((1<<i)&d) u=fa[u][i];	if(u==v) return u;	for(int i=M-1; i>=0; --i) if(fa[u][i]!=fa[v][i]) u=fa[u][i], v=fa[v][i];	return fa[u][0];}int main() {	read(n); read(m);	for(int i=1; i<n; ++i) add(getint(), getint());	dfs(1, 1); bz();	while(m--) printf("%d\n", lca(getint(), getint()));	return 0;}

 


联系
我们