最近公共祖先（LCA）

2024-03-25 09:59:10

Update：有问题请私信我，我会在4848小时内回复。

概念

最近公共祖先问题：简称LCALCA（Least Common AncestorsLeastCommonAncestors），指的给出一棵有根多叉树，询问x,yx,y的最近公共祖先。

例如上图中，44和33的LCALCA是22，88和33的LCALCA是11。

实现方法

朴素做法

如果x,yx,y在树中的深度不同，那么先将xx和yy跳到同一深度，然后直接枚举xx和yy的父亲，爷爷，爷爷的父亲...是否相等

例如，x=6,y=11x=6,y=11。

y:11->9y:11−>9

跳到同一深度

x:6->4->2->1x:6−>4−>2−>1

y:9->8->7->1y:9−>8−>7−>1

逐步向上跳，直到相遇。

妥妥的TLE。

倍增

前置知识：十进制整数的二进制唯一分解性质（自行百度）

首先，设f[k][i]f[k][i]表示kk的2^i2i倍祖先。如果这个节点不存在，那么我们可以将它设为00。

设rr为x,yx,y相遇要走的层数。（当然，我们并不知道rr）在朴素做法中，我们是一层一层向上跳。rr一定可以分解为一个二进制数。在rr的第jj个二进制位为1的时候，x,yx,y一起向上跳，就可以相遇了。

例如，r=5r=5。(5)_{10}=(1001)_{2}(5)10=(1001)2。所以，x,yx,y要先跳2^323层，再跳2^020层。如果再往上跳，那么x,yx,y就会一直相等了，而此时找到的，就并不是最近的公共祖先了。

代码（倍增）

预处理

设dep[i]dep[i]表示ii在树上的深度。树根的深度为00,即dep[root]=0dep[root]=0。这一步可以DFS遍历得到。

void dfs(int k,int father)//记录父亲节点
{
   dep[k]=dep[father]+1;
   for(register int i=1;i<=20;++i)//20要进行实际计算    
       f[k][i]=f[f[k][i-1]][i-1];//（注:这里^是次方的符号）记录2^x倍祖先，方便二进制拆分。很显然：2^(x-1)+2^(x-1)=2^x 如果2^x倍祖先不存在，那么为0（我们不用特判）
   for(register int i=head[i];i;i=edge[i].next)//邻接表遍历
{
       int v=edge[i].to;
       if(v==father)//如果是父亲，那么就不能访问
           continue;
       f[v][0]=k;  //2的零次方等于1，即父亲节点            dfs(v,k);//继续往下搜索
}
return;
}

对付询问

为了方便操作，我们不妨让dep[x]>dep[y]dep[x]>dep[y]。
```
 if(dep[x]>dep[y])std::swap(x,y);
```

利用前置知识二进制唯一分解性质将xx的深度调整与yy相同。

 for(register int i=20;i>=0;i--){
  if(dep[f[x][i]]>=dep[y])x=f[x][i];//这个语句的意思是，如果还没有到y的深度，就往上跳。如果要往上面跳五层才相遇，那么x就会在i=3和i=0的时候跳。（二进制拆分）
  if(x==y)return x;
  //如果x,y跳到了同一层，并且相等，那么LCA就是x了
}

还是利用二进制拆分思想，不断往上跳

 for(register int i=20;i>=0;i--)
  if(f[x][i]!=f[y][i])//如果不相遇才跳，相遇了的话我们就不能确定这个祖先是不是最近的啦
      x=f[x][i],y=f[y][i];

这时，我们已经跳到了LCA的底下一层，所以返回f[x][0]或者f[y][0]就好啦
```
 return f[x][0];
```
附注一句：其实二进制拆分思想是一个慢慢逼近的过程。如果往上跳这么多没有超过我就可以往上跳，否则我就换一个更小的来选择跳还是不跳。

最后附上【模板】最近公共祖先（LCA）完整的代码，希望大家有收获哦~

~~代码的正确打开方式：无视掉register,inline和read()。~~

# include <bits/stdc++.h>
# define rr register//使用了一个宏定义
const int N=500001;
int dep[N];//记录深度
int f[N][21];//记录2^x倍祖先
int head[N];//图论邻接表，自行百度
struct Edge
{
    int to,next;
}edge[N<<1];//邻接表存树
int n,m,sum,s;//n,m,s如题目所述。sum是邻接表的内容
inline void add(int x,int y)//邻接表建立边
{
    edge[++sum].to=y;
    edge[sum].next=head[x];
    head[x]=sum;
    edge[++sum].to=x;
    edge[sum].next=head[y];
    head[y]=sum;//记得是双向边
    return;
}
inline int read()//快速读入
{
    int res,f=1;
    char c;
    while((c=getchar())<'0'||c>'9')
        if(c=='-')f=-1;
    res=c-48;
    while((c=getchar())>='0'&&c<='9')
        res=res*10+c-48;
    return res*f;
}

void first_work(int k,int father)
{
    dep[k]=dep[father]+1;//深度是父亲+1
    for(rr int i=1;i<=20;++i)//预处理他的1~20倍祖先
        f[k][i]=f[f[k][i-1]][i-1];//k的2^(x-1)倍祖先的2^(x-1)倍祖先就是k的2^x倍祖先
    for(rr int i=head[k];i;i=edge[i].next)//邻接表遍历相连的边
    {
        if(edge[i].to==father)continue;//如果是它的父亲就不管，因为我们要搜索他的子孙
        f[edge[i].to][0]=k;//它的2^0倍（1倍）祖先就是k
        first_work(edge[i].to,k);//往下搜
    }
    return;//规范的写法
}
inline int lca(int x,int y)//找lca
{
    if(dep[x]<dep[y])std::swap(x,y);//让x深度较大
    for(rr int i=20;i>=0;i--){//记住，是倒序。因为我们要慢慢逼近
        if(dep[f[x][i]]>=dep[y])x=f[x][i];//如果还能往上跳，就跳
        if(x==y)return x;//x,y如果跳到了一层，并且相遇了，那么lca就是x
    }
    for(rr int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])//如果不相等，也就是还没有到lca的位置，我们就往上跳
            x=f[x][i],y=f[y][i];//往上跳
    return f[x][0];//因为往上跳的时候我们要求不相遇，所以只会跳到lca的底下一层。我们就要返回x的父亲或者y的父亲
}
int main()
{
    n=read();
    m=read();
    s=read();
    for(rr int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add(x,y);
    }
    first_work(s,0);//小技巧：s没有祖先，就把它的祖先设为0
    for(rr int i=1;i<=m;i++)//m次询问
    {
        int x,y;
        x=read();
        y=read();
        printf("%d\n",lca(x,y));//求出lca并输出就好啦
    }
    return 0;//代码规范
}

最后再说一句：请读者指出此篇文章的不足之处！谢谢！不懂的可以在洛谷上面私信我！作者地址

码农公寓

概念

实现方法

朴素做法

倍增

代码（倍增）

相关文章