【学习笔记】进阶算法——最近公共祖先 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，算出每个节点的深度，并记录下每个节点的父节点。
void DFS(int u,int Fath){
dep=dep+1,fa=Fath;
for(int v:g)if(v^fa)DFS(v,u);return;
}这样我们就 \(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\)。
if(dep<dep)swap(x,y);
while(dep>dep)x=fa;接下来就是求解 LCA 了。
由于 \(x\) 和 \(y\) 的深度已经相同，所以我们让 \(x\) 和 \(y\) 不断一个一个往上跳，直到 \(x=y\)。
while(x!=y)x=fa,y=fa;最后返回 \(x\) 即可。
所以整个 LCA 函数大概是这个样子：
int LCA(int x,int y){ if(dep<dep)swap(x,y);
while(dep>dep)x=fa; while(x!=y)x=fa,y=fa; 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）部分的代码就变成了这样：
void DFS(int u,int fa){
dep=dep+1,f=fa;
for(int i=0;f;i++)f=f];
for(int v:g)if(v^fa)DFS(v,u);return;
}其中 \(f_{i,u}\) 表示节点 \(u\) 往上跳 \(i\) 步后所处节点。如果跳爆了（树没有那么大）那么值为 \(0\)。
那么 LCA 求解过程中的两个 while 函数的时间复杂度就都可以得到改善啦！从 \(O(n)\) 一下变为 \(O(\log n)\)，很爽吧？
具体来说，就是利用 \(f\) 数组来跳跃。
细节见代码吧。
int LCA(int u,int v){
if(dep>dep)swap(u,v);
for(int i=20;i>=0;i--)
if(dep<=dep-(1<<i))v=f;
if(u==v)return u;
for(int i=20;i>=0;i--)
if(f!=f)u=f,v=f;
return f;
}即可。
然后最后跑一遍，恢复一下就行。
int x,y,lca;cin>>x>>y;lca=LCA(x,y);
d++,d++,d--,d]--;输出 \(ans\) 即可。
总结
LCA 两大特色，一个树上差分，一个树上前缀和。相比于后者，前者的应用要更广泛一些。
很多时候 LCA 也会用来辅助各种东西。
究其根源，LCA 就是用来计算树上两个节点的路径的长度的！当然啦，LCA 也很聪明，它支持存在边权/点权之类的附属条件的树哦！
这就是 LCA，图轮中的好伙伴！
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]