倍增求lCA

2024-03-28 19:55:28

什么是LCA

LCA(Least Common Ancestors),有一棵树，若结点z既是结点x的祖先也是结点y的祖先，且z的深度最大，那么称这个结点x是结点a,b的最近公共祖先。

倍增法是什么

其实求LCA，有一个极为朴素的方法，就是先比较两个结点的深度，然后dfs大的直到深度和小的一样，然后这两个结点一起dfs,直到找到同一个结点，而倍增则是利用了二进制拆分，将范围扩大一倍，从而加速操作，这个思想和st表很像，也要先预处理出一个表。

求\(f\)数组

我们需要预处理出一个数组\(f[i][j]\) 表示i的\(2^j\)辈的祖先，也就是x向根节点走\(2^j\)步到的结点，一般来说\(2^{20}\)就已经够了，我们可以用状态转移方程：\(f[i][j]=f[f[i][j-1]][j-1]\) 来求得f数组，我们可以推导一下如何求出这个方程：

特别地，如果这个结点的2^j辈没有结点那那么我们让\(f[i][j]=0\) ,\(f[i][0]\) 就是i结点的父亲，因为对于一个结点，它走\(2^j\)步,其实等同于它先走\(2^{j-1}\),再走\(2^{j-1}\)步,这样我们就推出了\(f[i][j]=f[f[i][j-1]][j-1]\)其中\(f[i][j-1]\)表示\(i\)的\(2^{j-1}\)辈祖先的位置，后面的\([j-1]\)可以认为让\(2^{j-1}\)辈祖先，走\(2^{j-1}\)步，这个方程很好理解，所以不需要去死记硬背。

dfs求深度，求f数组的代码

dfs(s,0);//s表示根节点的序号
void dfs(int u,int fa){//其实这个dfs真正要求的是当前结点的深度
  f[u][0]=fa;
  for(int i=1;i<=20;i++)
    f[u][i]=f[f[u][i-1]][i-1];//预处理当前结点的祖先
  dep[u]=dep[fa]+1;//深度会等于父亲结点+1
  for(int i=head[u];i;i=net[i]){//邻接表
    int v=ver[i];
    if(v==fa) continue;//对于双向边来说肯定有可能出现儿子走向父亲的边
    dfs(v,u);
}

求祖先

我们要知道的一点是，先走大步再走小步，为什么呢？我们可以这样想，如果先走小步，走到后面发现不需要走这一步这么办？那就只能回溯了，我们还可以换一种理解，我们在往箱子里塞东西时，肯定会先塞大的东西，然后用小的东西逐渐填满空隙。

Lca的步骤

我们先判断两个结点的深度，然后不断让更深的结点走，直到两个结点很接近了，这个思想其实和朴素求LCA是一样的。
让两个结点一起跳，知道他们的父亲相同

lca的代码

int lca(int x,int y){
  if(dep[x]<dep[y]) swap(x,y);//保证x更深
  for(int i=20;i>=0;i--)//逆序
    if(dep[f[x][i]]>=dep[y])//不断让这两个点接近，注意点1
      x=f[x][i];
  if(x==y) return x;//有可能这两个结点一开始就是祖辈关系
  for(int i=20;i>=0;i--)
    if(f[x][i]!=f[y][i]){//注意点2
      x=f[x][i];
      y=f[y][i];
    }
  return f[x][0];
}

注意

在上面的代码，标注了两个要注意的地方：

为什么是大于或等于，因为当出现等于的情况时就找到LCA了
这段代码可能会有些疑惑：“咦，上段代码都可以等于，为什么这段代码就不行呢(⊙o⊙)?”因为我们要求的是最近公共祖先。

码农公寓