【学习笔记】进阶算法——最近公共祖先 LCA

前置知识

• 树：树是一个特殊的图，其边通常为无向边，并且一共只有 \(n-1\) 条边，全图连通，通常有一个根。如果题目并没有明确指明某个节点为根，那么这棵树就是一棵无根树，这种情况下一般让 \(1\) 为根。
  
• 祖先：在树上，如果节点 \(y\) 是节点 \(x\) 的祖先，当且仅当 \(y\) 出现在从 \(x\) 到根的最短路径上。特别的，父节点是一个节点特殊的祖先节点。
  
• ST：一种不支持修改，仅支持查询操作的东西，耗费 \(O(n\log n)\) 的时间预处理，然后可以 \(O(1)\) 查询一个区间的最大值/最小值/最大公因数等。要求查询的东西满足结合律，并且如出现重叠部分不会错误。
  

最近公共祖先（LCA）是什么？

最近公共祖先，即 Least Common Ancestors，简称 LCA，表示树上两个节点 \(x\) 和 \(y\) 分别的祖先节点合集的交集中最深的节点。比如说：

在上图中，\(LCA(4,6)=1\)，\(LCA(7,14)=3\)，\(LCA(11,12)=7\)。
暴力求解 LCA

求解 LCA，有一种最坏时间复杂度 \(O(n)\) 的求解 LCA 的方案。
首先要进行预处理。以 \(1\) 为根节点跑一遍 DFS，算出每个节点的深度，并记录下每个节点的父节点。

1. void DFS(int u,int Fath){
2.     dep[u]=dep[Fath]+1,fa[u]=Fath;
3.     for(int v:g[u])if(v^fa)DFS(v,u);return;
4. }

复制代码

这样我们就 \(O(n)\) 得知了每个节点的深度 \(dep_u\) 以及每个节点的父节点 \(fa_u\)。
接下来就是求解 \(LCA(x,y)\) 了。
首先，我们先要保证 \(x\) 和 \(y\) 的深度相同。
不妨让 \(dep_x \ge dep_y\)（如果原本 \(dep_x < dep_y\) 那么 swap(x.y)）。接下来我们不停让 \(x=fa_x\)，直到 \(dep_x=dep_y\)。

1. if(dep[x]<dep[y])swap(x,y);
2. while(dep[x]>dep[y])x=fa[x];

复制代码

接下来就是求解 LCA 了。
由于 \(x\) 和 \(y\) 的深度已经相同，所以我们让 \(x\) 和 \(y\) 不断一个一个往上跳，直到 \(x=y\)。

1. while(x!=y)x=fa[x],y=fa[y];

复制代码

最后返回 \(x\) 即可。
所以整个 LCA 函数大概是这个样子：

1. int LCA(int x,int y){    if(dep[x]<dep[y])swap(x,y);
2. while(dep[x]>dep[y])x=fa[x];    while(x!=y)x=fa[x],y=fa[y];    return x;}

复制代码

非常简略，非常易懂。
LCA 这么简单吗？当然不是。
如何优化暴力 LCA 算法

刚才的 LCA 算法虽然求解一次时间复杂度还能接受，但如果处理 \(Q=10^5\) 这样的操作，\(n\) 也是 \(10^5\) 级别的，那么时间复杂度就完全爆炸了，不能接受，考虑优化。
时间复杂度的瓶颈在于两个 while 函数。我们是一个一个跳的，很慢。但如果我们按照 \(\log\) 的时间复杂度来算呢？如果我们每次跳 \(2^k\) 个呢？总之差值肯定是一个整数，拆成二进制后顶多也就二十来位。这样不就快多了？
但是处理的东西就复杂些。本来只需要存储自己的父节点即可，但现在要存储自己往上跳 \(2^0,2^1,2^2,\dots,2^k\) 的祖先节点。看上去很麻烦，这东西好实现吗？其实上很简单，这个思想就类似于 ST。只需要在 DFS 过程中，每枚举到一个节点 \(u\)，就花费 \(O(\log n)\) 的时间计算存储一下即可。
那么一开始的预处理（DFS）部分的代码就变成了这样：

1. void DFS(int u,int fa){
2.     dep[u]=dep[fa]+1,f[u][0]=fa;
3.     for(int i=0;f[u][i];i++)f[u][i+1]=f[f[u][i]][i];
4.     for(int v:g[u])if(v^fa)DFS(v,u);return;
5. }

复制代码

其中 \(f_{i,u}\) 表示节点 \(u\) 往上跳 \(i\) 步后所处节点。如果跳爆了（树没有那么大）那么值为 \(0\)。
那么 LCA 求解过程中的两个 while 函数的时间复杂度就都可以得到改善啦！从 \(O(n)\) 一下变为 \(O(\log n)\)，很爽吧？
具体来说，就是利用 \(f\) 数组来跳跃。
细节见代码吧。

1. int LCA(int u,int v){
2.     if(dep[u]>dep[v])swap(u,v);
3.     for(int i=20;i>=0;i--)
4.         if(dep[u]<=dep[v]-(1<<i))v=f[v][i];
5.     if(u==v)return u;
6.     for(int i=20;i>=0;i--)
7.         if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
8.     return f[u][0];
9. }

复制代码

即可。
然后最后跑一遍，恢复一下就行。

1. int x,y,lca;cin>>x>>y;lca=LCA(x,y);
2. d[x]++,d[y]++,d[lca]--,d[f[lca][0]]--;

复制代码

输出 \(ans\) 即可。
总结

LCA 两大特色，一个树上差分，一个树上前缀和。相比于后者，前者的应用要更广泛一些。
很多时候 LCA 也会用来辅助各种东西。
究其根源，LCA 就是用来计算树上两个节点的路径的长度的！当然啦，LCA 也很聪明，它支持存在边权/点权之类的附属条件的树哦！
这就是 LCA，图轮中的好伙伴！

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！