倍增法求lca（最近公共祖先）

佚名 5年前 (2019-08-04) 算法 1266人围观抢沙发百度已收录

倍增法求lca(最近公共祖先)

基本上每篇博客都会有参考文章，一是弥补不足，二是这本身也是我学习过程中找到的觉得好的资料

思路：

大致上算法的思路是这样发展来的。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

想到求两个结点的最小公共祖先，我们可以先把两个的深度提到同一水平，在一步一步往上跳，直到两个结点有了一个公共祖先，依照算法流程，这就是least common ancestor。

但是如果这样一步步地往上未免太让人着急，为了提高一下效率，便不再每次只跳一步，而跳\(2^i\)步。一般的，先这样蹦蹦跳跳跳上去直到两个结点相平，在两个一起这样蹦上去。

怎么确定这个i该是多少合适呢？

这里我们需要预处理一个数组f，f[u] [i]来表示结点u的第i代祖先，f[u] [0]表示结点u的父亲，这个数组用链式前向星（最近怎么老是它）加上dfs来预处理产生，十分便捷。那它有什么用呢？用在提升结点的时候，我们可以借助这个数组直接将结点提到他的合适的祖先上去。怎么才算合适的祖先？现假设求lca(s,t)

分两步，第一步是将低结点提到高结点（相对于叶节点）的深度上。这时候一个for循环从s的第20代祖先开始（为什么是二十代？可能一般的树达不到这个深度）,看能不能把s提上去后满足\(depth[s]>=depth[t]\)，不能满足就看第十九代祖先这样一直减少i，若满足了就把s提上去，还是继续减少i，直到两个结点最终相平。这个过程有个博客里讲的很形象（见参考文章），比喻成乌鸦喝水的过程，就是乌鸦先把体积大的（这里就是i值）放进水杯里，再逐渐减小放入物品的体积直到把水杯的水升上来，而不是先填沙子这种小颗粒的东西。这就是为什么i值要从大到小。

第二步是整体提升的过程，我们不知道该几步提升，在循环中的条件就变成了\(if(f[s][i]!=f[t][i])\)。也就是只要他两的祖先不一样就提升，祖先一样有两种可能，一种可能是节点是祖先但不是最小公共祖先，另一种可能是到了公共祖先。前一种出现在循环的开始，一开始想要提的深度比较多，所以很可能提到了公共祖先。这种情况不用管，继续减小i值，之后可能会由于满足\(if\)条件而经历一些两点提升的过程，最后不满足\(if\)条件了，说明两个已经有了最小公共祖先，这时候随意输出一个节点的父结点就行了。

算法完成，看看代码。如觉得不太清楚请看参考文章。

代码：

代码里有一些优化，把for循环改成了log_2+1数组，关于这个优化，我也不知道他优化在了什么地方，是从一篇博客看来的（见参考文章），我用了优化甚至吸了氧和没用优化没吸氧是一样的（(╯‵□′)╯︵┻━┻），都T了3个点，最后是加了读入优化（见上一篇博客）才过了。

#include <iostream>
#include <cstdio>
#define max_n 500005
using namespace std;
int n,m,s;//n为结点数，m为边数,s为根节点标号
int lg[max_n];//优化用到的预处理的数组，存log_2[i]-1
int f[max_n][23];//f[u][i]表示结点u的第i代祖先，其中f[u][0]为u的父结点
int depth[max_n];//节点深度
//链式前向星
int head[max_n];
struct edge
{
    int v;
    int next;
}e[max_n<<1];
int cnt = 0;
void add(int u,int v)
{
    ++cnt;
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
//快速读入模板
inline void read(int& x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f = 1;ch = getchar();}
    while('0'<=ch&&ch<='9') {x = 10*x+ch-'0';ch=getchar();}
    x = f?-x:x;
}
//dfs预处理出结点往上跳2^i的结点
void dfs(int u,int from)
{
    depth[u] = depth[from]+1;//比父结点深度加一
    for(int i = 1;1<<i<=depth[u];i++)//祖先结点要存在，不存在的默认为零
    {
        f[u][i] = f[f[u][i-1]][i-1];//f[u][i]的第u个结点第i-1代祖先的第i-1代祖先记为第i代祖先
    }
    for(int i = head[u];i;i=e[i].next)
    {
        int v = e[i].v;
        if(v==from) continue;//因为是无向边，判断不能反回父结点
        f[v][0] = u;//
        dfs(v,u);
    }
}
//求最近公共祖先
int lca(int s,int t)
{
    if(depth[s]<depth[t]) swap(s,t);//设s比t深
    while(depth[s]>depth[t])//若s比t深，不断上移s
    {
        s = f[s][lg[depth[s]-depth[t]]-1];//上移log_2[深度差]步，直到相平
    }
    if(s==t)//若t为s的祖先
    {
        return s;//则s,t的lca是t
    }
    for(int i = lg[depth[s]]-1;i>=0;i--)//待s,t相平后
    {
        if(f[s][i]!=f[t][i])//只要两公共祖先不等
        {
            s = f[s][i];//将二者上移
            t = f[t][i];
        }
    }
    /*for(int i = 20;i>=0;i--)
    {
        if(f[s][i]!=f[t][i])
        {
            s = f[s][i];
            t = f[t][i];
        }
    }*/
    return f[s][0];//直到最后两者公共祖先相等，记为lca
}
int main()
{
    read(n);
    read(m);
    read(s);
    for(int i = 1;i<=n;i++)//优化数组玄学构造法求log_2[i]+1
    {
        lg[i] = lg[i-1]+((1<<lg[i-1])==i);
    }
    for(int i = 1;i<n;i++)
    {
        int u,v;
        read(u);
        read(v);
        add(u,v);
        add(v,u);
    }
    dfs(s,0);
    int ans = 0;
    for(int i = 1;i<=m;i++)
    {
        int a,b;
        read(a);
        read(b);
        ans = lca(a,b);
        cout << ans << endl;
    }
    return 0;
}