最近公共祖先（LCA）
最近公共祖先就是多叉树上根节点到两点路径重复部分的深度最低的点
朴素
先让两点深度相同，然后同时向上找知道两点相同
1
2
3
4
5
6
| int lca(int x,int y){
if(d[x]<d[y])swap(x,y);
while(d[x]!=d[y])x=f[x];
while(x!=y)x=f[x],y=f[y];
return x;
}
|
倍增
可以发现，上面的算法时间复杂度为 $O(n)$，可以用倍增优化向上找祖先的过程
首先预处理倍增数组，f[x][i] 表示 x 的第 $2^i$ 个祖先节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int d[N];
int f[N][22];
void dfs(int u,int fa){
d[u]=d[fa]+1;
f[u][0]=fa;
for(int i=h[u];~i;i=ne[i]){
if(to[i]!=fa){
dfs(to[i],u);
}
}
}
void init(){
for(int i=1;i<22;i++){
for(int j=1;j<=n;j++){
f[j][i]=f[f[j][i-1]][i-1];
}
}
}
|
然后就可以优化查询，首先让两点同深度，然后让两点同时向上跳（注意，这里是跳到不是公共祖先的节点上），最后得到的点的祖先节点就是答案。
1
2
3
4
5
6
7
8
9
10
11
| int lca(int x,int y){
if(d[x]<d[y])swap(x,y);
for(int i=21;i>=0;i--){
if(d[f[x][i]]>=d[y])x=f[x][i];
}
if(x==y)return x;
for(int i=21;i>=0;i--){
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
}
return f[x][0];
}
|