倍增 LCA

Prologue

给定一棵有根树,若节点 zz 既是节点 xx 的祖先,也是节点 yy 的祖先,则称 zzx,yx,y 的公共祖先。在 x,yx,y 的所有公共祖先中,深度最大的一个称为 x,yx,y 的最近公共祖先,记为 LCA(x,y)\text{LCA} (x,y)
LCA(x,y)\text{LCA} (x,y)xx 到根的路径与 yy 到根的路径的交会点。它也是 xxyy 之间的路径上深度最小的点。

 

​如图,节点 4,64,6 的公共祖先有 2,12,1,它们的最近公共祖先是 22

一些性质

​根据倍增思想,可以设 f[i][j] 节点 ii 的第 2j2^j 辈祖先。并约定该节点不存时 f[i][j]=0。显然有:

  • f[i][0]ii 的父节点
  • 若树的深度为 nn,则 jlognj\leq\log n

实现过程

​倍增 LCA 的过程如下

  1. 对树执行遍历(BFS 效率较高),预处理出所有节点的深度 dd, 和其第 2j2^j 辈祖先,显然有 f[i][j+1]=f[f[i][j]][j]
  2. d[x]<d[y] 则交换 x,yx,y,使得 xx 处于 yy 之下,或与 yy 在同一深度。
  3. 尝试令 xx 等于它的 2j=logn,,1,02^{j=\log n,\dots ,1,0} 辈祖先。并不断检查 xxyy 的深度,若 d[x]>d[y] ,则不断令 x=f[x][j]
  4. x==y 则说明 xxyy 在同一条链上,且 LCA(x,y)=y\text{LCA}(x,y)=y
  5. 尝试令 x,yx,y 等于它的 2j=logn,,1,02^{j=\log n,\dots ,1,0} 辈祖先。若 f[x][j]!=f[y][j] ,则不断令 x=f[x][j] y=f[y][j] 。最后 f[x][0] 就是 LCA(x,y)\text{LCA}(x,y)

实践技巧

​由于 cmath 中的 log() 效率较低,在预处理和查询的过程中又需要反复使用 log1,,logn\log 1,\dots ,\log n 的值,可用考虑预处理出 log1,,logn\log 1,\dots ,\log n。这里提供一种优雅快速的实现。果然是打表出省一。

1
for(int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;

无需进行额外的初始化,数组定义为全局即可。

Talk is Cheap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <queue>
#include <cstdio>
const int _=5e5+1;
int n,m,s,fp=1,lg[_],d[_],hed[_],nxt[_<<1],ver[_<<1],f[_][20];
int read() {
int x=0;char c=getchar();
while(c<48||c>57) c=getchar();
while(c>47&&c<58) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x;
}
void link(int u,int v) {
ver[++fp]=v;nxt[fp]=hed[u];hed[u]=fp;
ver[++fp]=u;nxt[fp]=hed[v];hed[v]=fp;
}
void bfs() {
int u,v;d[s]=1;std::queue<int> q;q.push(s);
while(q.size()){
u=q.front();q.pop();
for(int i=hed[u];i;i=nxt[i]){
if(d[v=ver[i]]) continue;
d[v]=d[u]+1;f[v][0]=u;
for(int j=0;j<=lg[d[v]];++j)
f[v][j+1]=f[f[v][j]][j];
q.push(v);
}
}
}
int lca(int x,int y) {
if(d[x]<d[y]) x^=y^=x^=y;
while(d[x]>d[y]) x=f[x][lg[d[x]-d[y]]];
if(x==y) return x;
for(int i=lg[d[x]];i>=0;--i)
if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int main() {
n=read(),m=read(),s=read();
for(int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
for(int i=1;i<n;++i) link(read(),read());
bfs();
for(int i=0;i<m;++i) printf("%d\n",lca(read(),read()));
return 0;
}

Download

各种 LCA 的复杂度

预处理复杂度 询问复杂度 在线
倍增 LCA O(NlogN)O(N\log N) O(logN)O(\log N) 支援
HLD LCA O(N)O(N) O(logN)O(\log N) 支援
Tarjan LCA O(N)O(N) O(1)O(1) 不支援

​Tarjan LCA 的查询复杂度较低,但由于对询问进行离线也有一定时间开销,所以在实践中 Tarjan LCA 并没有比倍增 LCA 快多少。虽然 HLD LCA 的代码实现较为复杂,但在 HLD 的题目中如果需要计算 LCA,那 HLD LCA 是最好的选择。

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

笔记 算法

评论

您需要成为穿墙的邪仙以加载 Disqus。