浅学LCA

浅学LCA

一.LCA是什么

LCA的意思是最近公共祖先，就是两个节点的共同祖先中，离他们最近（离根结点最远）的节点。

如图，LCA(4,5) = 2；LCA(3,4) = 1;LCA(1,2) = 1。

二.LCA有什么用

当我们求树上两个点的最短路径时，我们可以知道，最短路径一定经过他们的最近公共祖先。所以，在处理与路径有关的问题时，我们会经常用到LCA。

三.LCA怎么求

1.暴力求解法

比如在本图中，要求LCA(3,5)。
我们可以先进行DFS，得到每个点的深度。
然后从深度更大的节点入手，让他一直向上跳到自己的父节点，当两个点的深度相同之后，check是否到了同一个位置，如果不是，两个点同时跳到自己的父节点，直到两点相遇。
在本图中5先跳到2,两个点深度相同，但却不在同一个位置，两个点同时向上跳，到达了1节点，两点相遇，他们的最近公共祖先就是1了。

2.树上倍增法

所谓倍增法，其实就是对刚才算法的一个优化，刚才算法在向上跳跃的时候复杂度大约为$O(deep)$。而倍增法可以让复杂度大致来到$O(log(deep))$ 我们的思路就是在向上跳的时候，要跳到$2^k$辈祖先 （1辈祖先是父节点）

准备

要做到这个，我们必须先dfs预处理得到节点深度信息和祖先信息。

void dfs(int x,int y = 0){
if(vis[x]) return ;//已经访问过，就已经得到deep和fa数组，返回 
vis[x] = true;
deep[x] = deep[y] + 1;//x是y的儿子节点，深度自然比y大1 
fa[x][0] = y;//fa[x][0]表示x的父亲节点,y就是x的父节点 
for(int i = 1;i <= l2[deep[x]];i ++){//见注释① 
fa[x][i] = fa[fa[x][i-1]][i-1];// 见注释② 
}
for(int i = head[x];i;i = e[i].next){//遍历所有的儿子 
dfs(e[i].to,x);//访问儿子节点，把自己记录成父亲 
}
}

注释①：
树的根到x的距离是deep[x]。
我们令n = deep[x]
我们知道

1. $2^{{\log }_{2}n}=n$
2. $\lfloor {\log }_{2}n\rfloor <={\log }_{2}n$
3. $2^{\lfloor {\log }_{2}n\rfloor }<=n$
4. $2^{\lfloor {\log }_{2}n\rfloor +1}>n$
   所以提前设置的时候，i <= l2[deep[x]]即可。
   注释②：

我们知道$2^x=2^{x-1}+2^{x-1}$
所以向上$2^x$ 级相当于向上$2^{x-1}$两次

至此，我们的准备工作就完成了。

开始

首先，让两个点先深度一致,也就是先让深层的向上爬
例如，x和y本来相差22的深度，现在x不用往上跳22次，只需要依次跳16、4、2个单位，3次便能达到与y相同的深度。

情况1

两者深度相等后，如果两个点已经相遇，那么相遇的这个点就是他们的LCA。

情况2

如果尚未相遇，我们再让它们一起往上跳。问题在于，如何确定每次要跳多少？
我们的思路是这样的，假如两个点的深度为$x$（根节点的深度为0），那么找到小于$x$的最大二的整数次幂$2^k$。然后尝试向上跳跃$2^k$。如果两个点还未相遇，先让两个点都向上跳$2^{k-1}$,k–，继续尝试，至少当k=0时，他们会在根节点相遇。（相遇之后，要进行下一步处理，因为可能走的步数多了，要回退）

for(int k=l2[deep[x]]; k>=0; k--)  
if(fa[x][k]!=fa[y][k])//如果发现x,y节点还没有上升到最近公共祖先节点
{
x=fa[x][k];//见文中
y=fa[y][k];//见文中
}
return fa[x][0];//必须返回x的父亲节点,也就是Lca(x,y)

题外话·回顾

我们知道，任何一个数，都可以由2的整数次幂组成

相遇之后，我们退回到原来的点，将k--。继续带入尝试，直到$k=1$为止。

注意！

在带入k尝试过程中吗，只要两个点不相交，就跳跃，k--，只要两个点相交，就k--。直到$k=1$为止。

如果你不知道为什么这么做【原理】

请回忆二进制的知识，我们现在相当于从最高位开始填数字，目标是让这个二进制数等于目标值，从最高位开始，填上1之后，比目标大了，求去掉这个1，去填下一位，比目标小了，就填上1，继续填下一位。

有人要问了：如果填了刚好相等呢？
我们的处理方式是，这一位填0，后面继续填写（自然都是1）。很容易发现一个问题，得到的答案会比预期少1.
我们看代码，最后返回的都是两个点的父亲节点。填写1的要求是，填上1之后，依然比预期值小。什么意思？也就是相当于，最后无论如何都加一个1上去，对于别的情况（全程没有刚好到LCA），最后一位填了1会等于目标值，只能填0，缺1，再加一，刚刚好。而有过填1刚好相等的（中途到过LCA），最后一位填了1还缺1，最后一位会填1，缺1，再加一，刚刚好。

原文地址：https://blog.csdn.net/Eric_dhy/article/details/149806136

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！