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(\operatorname{LCA}(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];
}