對於樹上倍增LCA的復習

Posted by czy_ on October 2, 2019

今年一年之内數場比賽都考到了樹上倍增LCA。（可見其之重要性）

於是，我們不如來復習一波。。

LCA（Least Common Ancestors）

即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。

常见解法一般有三种

这里讲解一种在线算法—倍增

首先我们定义fa[u][j]表示结点u的第2^j祖先

那么要怎么求出全部的fa数组呢

不难发现fa[u][0]就是u的父亲结点

这些父亲结点我们可以直接初始化

对于其他结点则有

fa[u][j]=fa[ fa[u][j-1] ] [j-1]

什么意思呢

u的第2^(j-1)祖先的第2^(j-1)祖先 就是u的第2^j祖先（有点像快速幂那样分解）

预处理各节点深度+初始fa[u][0]

void dfs(int u,int pa)
{
    dep[u]=dep[pa]+1;
    fa[u][0]=pa;
    for(int i=head[u];i;i=E[i].nxt)
    {
        int v=E[i].v;
        if(v!=pa) dfs(v,u);
    }
}

预处理fa数组

for(int i=1;(1<<i)<=n;i++)
for(int u=1;u<=n;u++)
fa[u][i]=fa[ fa[u][i-1] ][i-1];

预处理之后怎么求解LCA(u，v)呢

我么先假定dep[u]>dep[v]

则两点深度差 d=dep[u]-dep[v]

现在我们要做的是把u升到与v同样的深度

怎么做呢？ 先贴代码

for(int i=0;(1<<i)<=d;i++)
if( (1<<i) & d ) x=fa[x][i];

对于任意一个d

我们都能将其分解为d=2^p1+2^p2+……2^pi

这可以用二进制实现

例如d=5 ，5的二进制是101

我们将其分解为100+1

而100的十进制是4，1的十进制是1！！！

4=2^2 1=2^0

5=2^2 +2^0

是不是好神奇！！！！(欢呼)

应用到这里

就是查询d的二进制哪些位是1

查询到第i位为1

我们就将u向上升2^i个深度

这样一定能升到与v同深度

(注意二进制最右边一位是第0号位)

if( (1<<i) & d )

这一段用来检查d的二进制下第i位是否为1

抬升到相同高度后就可以开始查询LCA了

同样先上代码

for(int i=(int)log(n);i>=0;i--)
{
    if(fa[x][i]!=fa[y][i])
    {
        x=fa[x][i];
        y=fa[y][i];
        }
    }
    return fa[x][0];
}

大体思路就是

从u和v最远的祖先开始

如果u的第2^i祖先等于 v的第2^i祖先，就不移动

否则u和v同时上移2^i个深度

最后u的父亲一定是u和v的LCA

(其实蒟蒻不是特别理解其中的玄学道理，但手动模拟了几组发现真的是这样）

妙啊~妙啊~

最后贴上一份完整代码

模板题传送门啦~啦~啦~

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return x*f;
}

void print(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

int n,m,s;
int tot;
struct node{int v,nxt;}E[1000010];
int head[1000010];
int fa[5000010][25];
int dep[1000010];

void add(int u,int v)
{
    E[++tot].nxt=head[u];
    E[tot].v=v;
    head[u]=tot;
}

void dfs(int u,int pa)
{
    dep[u]=dep[pa]+1;
    fa[u][0]=pa;
    for(int i=head[u];i;i=E[i].nxt)
    {
        int v=E[i].v;
        if(v!=pa) dfs(v,u);
    }
}

int lca(int x,int y)
{
    if(dep[x]-dep[y]<0) swap(x,y);//将u设为深度较深的结点
    int d=dep[x]-dep[y];

    for(int i=0;(1<<i)<=d;i++)
    if( (1<<i) & d ) x=fa[x][i];//抬升

    if(x==y) return x;//抬升后x==y，则其LCA就是y(或此时的x)
    else
    {
        for(int i=(int)log(n);i>=0;i--)
        {
            if(fa[x][i]!=fa[y][i])
            {
                x=fa[x][i];
                y=fa[y][i];
            }
        }
        return fa[x][0];
    }
}

int main()
{
    n=read();m=read();s=read();
    for(int i=1;i<=n-1;i++)
    {
        int x=read(),y=read();
        add(x,y);add(y,x);
    }

    dfs(s,-1);
    //无根树转有根树，在这里调用是pa要设为-1

    //预处理fa数组
    for(int i=1;(1<<i)<=n;i++)
    for(int u=1;u<=n;u++)
    fa[u][i]=fa[ fa[u][i-1] ][i-1];

    while(m--)
    {
        int x=read(),y=read();
        int ans=lca(x,y);
        print(ans); printf("\n");
    }
    return 0;
}