[LCA]最近公共祖先

前言

LCA(Least Common Ancestors)，即最近公共祖先，是指在有根树中，某两个顶点U和V的最近公共祖先。

例如这一刻有根树，LCA(2, 3)是1，LCA(6, 9)是3。
这一篇blog会介绍3种如何寻找LCA的算法。

Tarjan

Tarjan(Robert Endre Tarjan)是一位著名的计算机科学家，曾在1986年获得Turing奖。一般提到Tarjan算法都会先想到强连通分量的那一个算法，但是Tarjan也发明了一个算法求解LCA问题。

要理解这一个算法需要先学会并查集，不然的话可能会有一点的小问题。Tarjan算法是强制离线的，也就是要先把所有的询问都存起来，然后再一起求解，不能边询问边回答。

Tarjan算法利用了DFS和并查集一起求解。

DFS中主要做了以下几件事情：

• 标记自己已访问（可以用一个vis数组标记）
• 在并查集中把自己作为自己的父节点，即fa[rt]=rt
• DFS所有的儿子节点，并在DFS结束后将儿子结点在并查集中的指向自身，即fa[son]=rt
• 处理和自身有关的询问，若另一个顶点在并查集中的指向不为-1(初始化时将并查集所有的结点设为-1)，则LCA(rt, other)就为fa[other]

好像干说也不知道是怎么一回事，还是看图直接一点。

就用这一颗树来做例子吧，我们分别要求LCA(2, 4)、LCA(6, 9)和LCA(6, 8)。

将fa数组初始化为-1

DFS从1开始，fa[1]=1

然后遍历1的儿子顶点2，fa[2]=2

然后遍历2的儿子顶点4，fa[4]=4

这时候4没有儿子顶点了，所以要开始处理与4有关的询问，之前我们说过要求LCA(4, 2)，这时候fa[2]!=-1,所以LCA(4, 2)=fa[2]=2,然后将4的父亲改为2,fa[4]=2

继续遍历2的儿子顶点5，fa[5]=5

继续遍历5的儿子顶点8，fa[8]=8

然后开始处理关于8的询问，LCA(6, 8)，因为fa[6]=-1，所以我们先暂时不管，等遍历到6时再处理这一个询问，将顶点8的父亲改为5,fa[8]=5

然后回到顶点5，处理关于5的询问，没有，将顶点5的父亲改为2，回退到2

回退到顶点1，将fa[2]改为1

然后继续遍历顶点3，然后到顶点6，这里和上面的修改一样，偷懒省略一点点

开始处理关于6的询问，求LCA(6, 8)，因为fa[8]！=-1,然后就根据并查集的思想去找8的根节点，找到是1，所以LCA(6, 8)=1。求LCA(6, 9)时，因为fa[9]=-1，所以先暂时不管。将顶点6的父亲改为3，回退到3

继续遍历到顶点7然后到顶点9

然后处理关于9的询问，求LCA(6, 9)，找到6这时候的祖先为3，所以LCA(6, 9)=3，然后回退到7回退到3

最后回退到1，结束

Tarjan求解LCA的过程就是这样，多看几遍流程就懂了，算法实现蛮容易的，就不写代码了

倍增

求LCA容易想到一个暴力方法就是，先将较深的顶点一步步跳到和较浅的顶点一样深度，判断他们是否相等，相等的话说明较浅的顶点就是他们的最近公共祖先，如果不相等的话，再一起一步步向上跳，直到相等为止。

倍增和这个暴力法的区别就是，倍增不是一步步跳的，它每次跳2^i步，比如1、 2、 4、 8……等。

但是现在有一个问题就是，我们怎么知道每一个顶点向上跳1、 2、 4……步到达的顶点是多少呢？所以我们要预处理每一个顶点向上跳1、 2、 4……步之后到达的顶点是什么。

预处理是用dp做的，假设fa[i][j]表示顶点i向上走2^j步之后到达的顶点。那很显然fa[i][0]就是自己的父亲。fa[i][1]就是向上跳了两步，是自己的爷爷。fa[i][2]向上跳了4步，到达了爷爷的爷爷。我们可以发现fa[i][1]=fa[fa[i][1-1]][1-1]，fa[i][2]=fa[fa[i][2-1]][2-1]。第一条等式是找自己的爷爷，相当于是父亲的父亲，第二条等式是爷爷的爷爷，所以先向上跳两步到爷爷，爷爷再向上跳两步到达爷爷的爷爷。

所以我们找出了状态转移方程为fa[i][j] = fa[fa[i][j-1]][j-1]，用dp很容易就预处理好。

用洛谷的板题来看看代码怎么写吧。

洛谷P3379

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
typedef pair<int, int> P;
const int maxn = 5e5+5;
const ll mod = 1e9+7;

vector<int> son[maxn]; // 存储儿子顶点
// dep[i]表示顶点i的深度，n个顶点，m个询问，rt为树根，fa数组用来预处理顶点i向上跳2^j步之后的顶点
int dep[maxn], n, m, rt, fa[maxn][20];
int v[maxn]={0}; // 是否访问标记

// pre是父顶点，rt是当前顶点
void dfs(int pre, int rt)
{
    dep[rt] = dep[pre]+1; // 当前顶点的深度为父顶点加一
    fa[rt][0] = pre; // 当前顶点向上跳一步为父顶点
    v[rt] = 1; // 访问
    // dp预处理
    for(int i=1;i<=19;i++)
        fa[rt][i] = fa[fa[rt][i-1]][i-1];
    // 继续dfs
    for(int i=0;i<son[rt].size();i++)
        if(v[son[rt][i]]==0)
            dfs(rt, son[rt][i]);
}

// 求解LCA(a, b)
int lca(int a, int b)
{
    // 如果a较浅，则交换a， b的值
    if(dep[a] < dep[b])
        swap(a, b);
    // 从2^19开始看看能不能向上跳（19是根据数据范围大小决定的）
    for(int i=19;i>=0;i--)
    {
        // 如果当前深度差大于2^i的话，就可以把a向上跳
        if(dep[a]-dep[b] >= (1<<i))
        {
            a = fa[a][i];
        }
    }
    // 判断当a和b同一个深度时是否为同一个顶点
    if(a==b)return a;
    // 一起向上跳
    for(int i=19;i>=0;i--)
    {
        // 如果向上跳2^i不相等的话，就是还没到达公共祖先的时候就一起跳
        if(fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    // 结束for循环的时候两个顶点还差1步就到达最近公共祖先了，所以返回fa[a][0]
    return fa[a][0];
}

int main()
{
    scanf("%d%d%d", &n, &m, &rt);
    for(int i=1;i<n;i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        son[a].push_back(b);
        son[b].push_back(a);
    }
    memset(fa, 0, sizeof(fa));
    memset(dep, inf, sizeof(dep));
    v[0]=1;
    dep[0] = 0;
    dfs(0, rt);
    for(int i=1;i<=m;i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}

倍增还是蛮好理解的，不算很难。

RMQ

RMQ(Range Minimum/Maximum Query)，即区间最值查询，用来查询一段区间的最大值最小值信息，容易想到的是ST表、树状数组、线段树等数据结构。

LCA是在树上做操作，难免有一些麻烦，所以我们考虑能不能够把树用线性表示。答案是可以的，我们用DFS序将树转化为线性的。

所以将LCA问题转化为RMQ问题用到了DFS序和ST表。

DFS序

DFS序就是对一颗树进行DFS之后得到的一串序列。

DFS序有两种：

• 仅在第一次经过和最后退出时记录该顶点的序号
• 每一次经过该顶点都记录顶点的序号

在这里我们选第二种DFS序，用下面这一颗树做例子。

得到的DFS序为1、 2、 4、 4、 2、 5、 8、 8、 5、 2、 1、 3、 6、 6、 3、 7、 9、 9、 7、 3、 1，跟着图看一遍就能看懂这个DFS序怎么来的了。

ST表

ST表是一种O(nlogn)预处理O(1)查询的数据结构，其实ST表和倍增里面的fa数组类似，也是用dp来做预处理。

在这里我们维护的是最小值，所以我也用最小值来举例。

st[i][j]表示的是从i开始，长度为2^j这一段区间里面的最小值。那么如何状态转移呢？st[i][j] = min(st[i][j-1], st[i+(1«(j-1)][j-1])。自己画个图看看是不是这么一回事。

假设我们要查询区间[l, r]的最小值要怎么做？区间的长度为r-l+1，我们要在st表中找两端区间能够覆盖住[l, r]，因为我们的st表表示的长度都是2^i那么长，那这一段区间找两段长度为k = log2(r-l+1)来进行覆盖。所以查询[l, r]的最小值就为min(st[l][k], st[r-(1«k)+1][k])，这样就轻松的实现了O(1)查询。

放一个st表的板子

int st[maxn][20];
void st_init()
{
    for(int i=1;i<=n;i++) st[i][0]=a[i]; // 长度为1的区间最小值党委就为自身
    // 预处理从i开始，长度为2^j的区间
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}

int query(int l,int r)
{
    int k=log2(r-l+1);
    return min(st[l][k],st[r-(1<<k)+1][k]);
}

LCA转RMQ

现在我们知道如何用DFS序将树转化为线性结构，如何用ST表来查询区间最小值。那如何将LCA问题转化为RMQ问题呢？我们的ST表是根据得到的DFS序来做预处理，存储的是从i开始，长度为2^j这一段区间里面深度最小的顶点在DFS序中的位置。

所以我们还需要一个记录深度的dep数组，一个记录DFS序的vis数组，一个记录顶点i第一次在vis数组出现的位置的id数组。

查询LCA(a, b)时就在DFS序中，找a和b第一次出现的位置之间的这一段区间里面深度最小的顶点，该顶点就是a和b的最近公共祖先。

同样用刚刚洛谷的那一个板题来看看代码怎么写吧。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
typedef pair<int, int> P;
const int maxn = 5e5+5;
const ll mod = 1e9+7;

vector<int> g[maxn]; // 存图
// dep记录DFS序中每一个顶点的深度， vis记录DFS序， id记录顶点i第一次在DFS序中的位置， st表
int dep[maxn<<1]={0}, vis[maxn<<1]={0}, id[maxn]={0}, st[maxn<<1][25];
// dfs序计数用，看代码能理解
int dfs_c=1;

// 父顶点为pre， 当前顶点为now， 当前深度为d
void dfs(int pre, int now, int d)
{
    id[now] =  dfs_c; // now顶点在DFS序中第一次出现的位置是dfs_c
    dep[dfs_c] = d; // 记录now的深度
    vis[dfs_c++] = now; // DFS序中第dfs_c个顶点是now，同时将dfs_c加一
    // 遍历now的儿子
    for(int i=0;i<g[now].size();i++)
    {
        // 因为存图是存双向变，所以这里要做一个判断
        if(g[now][i]!=pre)
        {
            // dfs自己的儿子顶点
            dfs(now, g[now][i], d+1);
            // 回退到now时也要在DFS序中记录，同时dep数组也要记录深度，但是id数组就不需要更新了，因为这里不是 第一次访问now顶点了
            vis[dfs_c] = now;
            dep[dfs_c++] = d;
        }
    }
}

// 预处理st表
void getSt(int n)
{
    for(int i=1;i<=n;i++)
        st[i][0] = i;
    for(int j=1; (1<<j)<=n; j++)
    {
        for(int i=1;i+(1<<j)<=n; i++)
        {
            int a = st[i][j-1], b = st[i+(1<<(j-1))][j-1];
            // 注意这里有一点点不同，st表要记录深度最小的顶点在DFS序中的位置。
            if(dep[a] < dep[b])
                st[i][j] = a;
            else st[i][j] = b;
        }
    }
}

// 查询DFS序中区间[l, r]深度最小的顶点在DFS序中的位置
int query(int l, int r)
{
    int k = log2(r-l+1);
    int a = st[l][k];
    int b = st[r-(1<<k)+1][k];
    // 返回深度较小的那一个顶点在DFS序中的位置
    if(dep[a]<dep[b])return a;
    else return b;
}

// 求LCA(a, b)
int lca(int a, int b)
{
    int x, y;
    // 查找a和b在DFS序中第一次出现的位置
    x = id[a], y = id[b];
    // 小的那一个作为左边界， 大的作为右边界
    // 返回具体的顶点序号
    if(x>y)return vis[query(y, x)];
    else return vis[query(x, y)];
}

// 检查用的
void check(int n)
{
    for(int i=1;i<=dfs_c;i++)cout<<dep[i]<<" ";cout<<"\n\n";
    for(int i=1;i<=dfs_c;i++)cout<<vis[i]<<" ";cout<<"\n\n";
    for(int i=1;i<=n;i++)cout<<id[i]<<" ";cout<<"\n\n";
}

int main()
{
    int n, m, rt;
    scanf("%d%d%d", &n, &m, &rt);
    for(int i=1;i<n;i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0, rt, 1);
    getSt(dfs_c);
    //check(n);
    for(int i=1;i<=m;i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}

END

LCA问题还算是蛮常见的吧，溜了溜了～