什么是LCA?

最近公共祖先,顾名思义,最近的公共祖先。不懂什么意思?我们来举一些例子你就懂了

在第29届国际信息学奥林匹克竞赛国家队选拔赛暨精英赛(CTSC)中,*工大附中刘承奥同学为陕西省赢得唯一的一枚金牌,另有2名同学荣获得铜牌,取得陕西省在该项赛事上近十年来的最好成绩,为陕西省、为*工大附中争了光。

没错这就是LCA,LCA orz

Emmm我们先跳过意外与算法重名或者说是天生注定的姓名加成的巨佬,说一下正经的最近公共祖先:

还是这张熟悉的图

在这张图里,以①为根,可以举一些例子: ⑥和③的LCA是③ ④和⑤的LCA是② ⑥和⑧的LCA是① ……

所以我想不用多解释,LCA的含义已经很清楚明白了。

怎么求LCA

树上倍增

我们可以由倍增的方式求两个节点的LCA,不过我们由浅入深,先不说倍增,先想一个通俗易懂的算法,还是这张图:

如果我们要求⑥和⑧的公共祖先怎么办,别给我说瞪眼法,机器不会的,除非你在OI里写个AI出来!

第一反应首先想到的最简单最暴力的应该是这样的吧:

  1. 判断⑥和⑧两个节点哪个深度更深,从更深的一个节点开始向上爬,直到与另一个节点深度相同。
  2. 当爬到与另一个节点深度相同之后,从两个位置同时向上每次爬一个深度,一直爬一直爬……
  3. 有一天你发现他们在一个节点邂逅了,太棒了他们找到LCA了。

通俗易懂是不是?明白这一点之后,树上倍增就很简单了,它只是对这种算法的二分优化罢了。

为了优化效率,我们可以考虑让他们每次跳\(2^k\)的深度,首先先来一个预处理,设二维数组\(f_{i,i}\)表示节点i向上走\(2^j\)次所到达的祖先,那么很容易的我们可以写出来这样子的转移方程: $$f_{i,0}=fa_i,\\ 从上面的式子得出:f_{i,j}=f_{f_{i,j-1},j-1}$$ //其中\(fa_i\)表示i节点的父亲

那么我们就可以轻松的用上面的递推式预处理,这个递推的时间复杂度是\(O(n\ log_2n)\)的。很优秀的复杂度。预处理后我们就要开始倍增了。

1、将a,b移动到相同的深度:

假设a比b的深度更大(事实上在写代码的时候也是这样假设的,若\(deep(b)>deep(a)\),\(swap(a,b)\)即可),这个时候我们要让a向上爬,方法是从适当的大小开始逆序枚举i。

因为是倍增,所以\(i=20\)的时候,一次就跳了\(2^20\)即1048576层,这对于99.99%的树都能跳到树根了,况且这么大的树用倍增LCA那是T定了,所以一般我们的i的上限可以取在10~20区间上合适的值,其实仔细想想这个i的上线应该取在\(ceil(log_2n)\)吧?我没有证明,这是我猜的!

枚举过程中,如果\(deep[f[a][i]]<deep[b]\),那么我们就向上跳到fa[a][i]。

为什么如果 \(deep[f[a][i]]<deep[b]\) 才往上跳呢?为什么不直接跳到它上面?因为我们是要首先让\(deep[a]=deep[b]\),由于类似二分的原理,我们的a最终会跳到\(deep[a]=deep[b]+1\)的位置,只要再往上走一步就和b相同深度了

2、特判:

如果在a爬深度的过程中突然发现,\(f[a][k]竟然等于b\),那么LCA结束,b就是a,b的LCA,跳过第三步

3、a,b幸福地一起爬深度

方法和a单独向上爬的时候的倍增方法一样,最终a,b都会在\(deep[lca]+1\)的位置上,所以他们的LCA就是\(fa_a或者fa_b\),这是同一个东西,即他们的公共祖先。

例题和AC代码

例题: https://www.luogu.org/problem/SP14932

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int M=2010; 
bool vis[M];
int cnt,n,m,q,rt;
int head[M<<1],fa[M],deep[M];
int f[M][20];
struct edge{
    int to,nxt;
}e[M<<1];

int Read(){
    char ch=getchar();
    int x=0;
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}

void Add(int x,int y){
    cnt++;
    e[cnt].to=y;
    e[cnt].nxt=head[x];
    head[x]=cnt;
}

void Init(){
    cnt=0;
    memset(head,0,sizeof(head));
    memset(vis,false,sizeof(vis));
    memset(deep,0,sizeof(deep));
    memset(head,0,sizeof(head));
    memset(f,0,sizeof(f));
    memset(fa,0,sizeof(fa));
}

void DFS(int x){
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        f[v][0]=x;
        deep[v]=deep[x]+1;
        DFS(v);
    }
}

int LCA(int a,int b){
    if(deep[a]!=deep[b]){
        if(deep[a]<deep[b])
            swap(a,b);
        for(int i=11;i>=0;i--)
            if(deep[f[a][i]]>=deep[b])
                a=f[a][i];
    }
    if(a==b) return a;
    for(int i=11;i>=0;i--)
        if(f[a][i]!=f[b][i])
            a=f[a][i],b=f[b][i];
    return f[a][0];
}

int main(){
    int T=Read();
    for(int num=1;num<=T;num++){
        Init();
        n=Read();
        for(int i=1;i<=n;i++){
            m=Read();
            for(int j=1;j<=m;j++){
                int x=Read();
                Add(i,x);
                vis[x]=1;
            }
        }
        for(int i=1;i<=n;i++)
            if(!vis[i]){
                rt=i;
                break;
            }
        deep[rt]=1;
        DFS(rt);
        for(int j=1;j<=16;j++)
            for(int i=1;i<=n;i++)
                f[i][j]=f[f[i][j-1]][j-1];
        q=Read();
        printf("Case %d:\n",num);
        for(i=1;i<=q;i++){
            int x=Read(),y=Read();
            printf("%d\n",LCA(x,y));
        }
    }
    return 0;
}

 

什么是一道破题调一天啊?我写这个代码都放弃AC率了

RMQ

区间最值查询 RMQ

Tarjan

不会。。。

0 0 votes
文章评分

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

0 评论
Inline Feedbacks
View all comments