LCA问题

LCA

LCA 的问题是很经典的，我这一次就来讲解一下 LCA 的求法，就先从一道模板题入手吧

题目

P3379 【模板】最近公共祖先（LCA）

输入格式

第一行包含三个正整数 \(N,M,S\) 分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 \(N-1\) 行每行包含两个正整数 \(x, y\) 表示 \(x\) 结点和 \(y\) 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 \(M\) 行每行包含两个正整数 \(a, b\) 表示询问 \(a\) 结点和 \(b\) 结点的最近公共祖先。

输出格式

输出包含 \(M\) 行，每行包含一个正整数，依次为每一个询问的结果。

说明/提示

对于 \(30\%\) 的数据，\(N\leq 10，N \leq 10\)。

对于 \(70\%\) 的数据，\(N\leq 10000，N \leq 10000\)。

对于 \(100\%\) 的数据，\(N\leq 500000 ， N \leq 500000\)

方法

LCA 的一些性质

• 两点的距离 ： $ d(u,v) = h(u) + h(v) + h((u,v) )$ ，\(h\) 代表某一点的深度
• 两点的最近公共祖先必定处在树上两点间的最短路上；

朴素算法

首先，我们想到最暴力的方法，先把整个树 DFS 一下，顺便将每个点的深度记录下来，将要查找的两个点中每次找深度最大的点，然后向上跳一格，最后两个点一定会相遇，相遇的点就一定是他们的 LCA 。

下面是 DFS 的代码

void dfs(int u,int fa){     // fa 为父亲节点，u 为当前节点， dep 为节点深度
    f[u] = fa;
    dep[u] = dep[fa] + 1;   // 因为是 DFS ，每个节点是从它的父亲来的，父亲与儿子的深度相差 1 
    for(int i=head[u];i;i = nex[i]){        // 链式前向星
        int v = to[i]; 
        if(v != fa)
            dfs(v,u);
    }
}

然后是 LCA 的核心代码 ：

while(x != y){
        if(dep[x] >= dep[y])    x = f[x];
        else y = f[y];
    }
    return x;

很简单，就不详细讲了， 预处理时间复杂度是 \(\mathcal{O}(n)\) ， 单次查询时间复杂度为 \(\Theta(n \log n)\) （随机树上) ，时间有点慢，遇到大数据就不行了，我们需要优化

倍增 LCA

这里先来了解一下倍增（更容易理解），顾名思义，一倍一倍的增加，就比如一步一步跳 7 格，但是我们可以先跳 \(2^2= 4\) 次，再跳 \(2\) 次，最后跳 \(1\) 次，原本需要跳 7 次，通过倍增只需要跳 3 次。

这里可以倍增首先基于一个推论 ：

• 任意整数可以表示成若干个 2 的次幂项的和

  \(eg. 7 = 2^2 + 2^1 + 2^0\)

  \(10 = 2^3 + 2^1\)

下面来讲一下倍增 LCA :

显然可以将一步一步跳变成倍增，在 DFS 时可以通过 \(2^i = 2^{i-1}+2^{i-1}\) 预处理 \(fa_i\) 的位置。

在查询时可以从小到大倍增（\(2^0,2^1,2^2\dots\)）来将 \(u,v\) 跳到同一深度，在同时 跳的时候从大到小倍增（\(2^i,2^{i-1}\dots 2^1,2^0\)），如果两个父亲不一样，就跳，那么最后的 LCA 是 \(fa_0\)

倍增 LCA 预处理时间复杂度为 \(\mathcal{O}(n \log n)\) ，单次查询时间为 \(\mathcal{O}(\log n)\) 。

这个时间复杂度大部分题目都是可以接受的。

代码：

void dfs(int u,int v){
    dep[u] = dep[v] + 1;
    fa[u][0] = v;
    for(int i=1;i<=19;i++)
        fa[u][i] = fa[fa[u][i-1]][i-1];
    for(unsigned int i=0;i<G[u].size();i++){
        if(G[u][i] == v)    continue;
        dfs(G[u][i],u);
    }
}

int LCA(int x,int y){
    if(dep[x] > dep[y])        swap(x,y);
    int tmp = dep[y] - dep[x];
    for(int i=0;tmp;i++,tmp >>= 1)
        if(tmp & 1)
            y = fa[y][i];
    if(x == y)    return x;
    for(int i=19;i>=0 && x != y;i--)
        if(fa[x][i] != fa[y][i]){x = fa[x][i];y = fa[y][i];}
    return fa[x][0];
}