最近公共祖先 LCA

什么是LCA？

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

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

~~没错这就是LCA，LCA orz~~

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

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

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

怎么求LCA

树上倍增

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

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

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

判断⑥和⑧两个节点哪个深度更深，从更深的一个节点开始向上爬，直到与另一个节点深度相同。
当爬到与另一个节点深度相同之后，从两个位置同时向上每次爬一个深度，一直爬一直爬……
有一天你发现他们在一个节点邂逅了，太棒了他们找到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

不会。。。