【学习笔记】倍增LCA

LCA问题：给定一颗 $n$ 个结点的有根树，有 $m$ 次询问，每次询问给出结点 $a,b$ ，求 $a,b$ 的最近公共祖先。此类问题通称 LCA 。

暴力

一次一次把 $a,b$ 向上提，知道 $a$ 与 $b$ 相等为止。

倍增加速

在上面暴力的思想中，是一步一步向上跳的。

倍增的核心思想就是 $2^j$ 步 $2^j$ 步向上跳。

我们需要先处理出第 $i$ 个点的第 $2^j$ 个祖先。

如何求出？

设 $f_{i,j}$ 为第 $i$ 个点向上跳 $2^j$ 后所处的位置，根据初一学习的幂的性质，我们认为第 $i$ 个点向上跳 $2^j$ 后所处的位置就是第 $i$ 个点向上跳 $2^{j-1}$ 后再向上跳 $2^{j-1}$ （ $2^{j-1}+2^{j-1}=2^j$ ）。

所以我们有：

$\text{令}x=f_{i,j-1},\text{则} f_{i,j}=f_{x,j-1}$

可以递推出来：

void dfs(int u, int fa) //当前是第 u 个结点，u 的父亲是 fa
{
    d[u] = d[fa]+1;  /顺便计算深度
    for(int i=1; (1<<i) <= d[u]; i++) //(1<<i)就是 2^i ，枚举2的次幂不能超过当前结点的深度
        f[u][i] = f[ f[u][i-1] ][i-1];

    for(int i=head[u]; i; i=nxt[i])
    {
        int v = ver[i];
        if(v == fa) continue;
        f[v][0] = u;
        dfs(v, u);
    }
}

我们有了 $f$ ，可以干啥呢？

假设要求 $\text{LCA}(a,b)$ ：

我们需要先把 $a,b$ 弄成同一深度，方便待会“一起跳”。

那么为了把 $a,b$ 弄成同一深度，显然需要把那个深度更深的结点不断向上跳，直到深度等于另一个结点为止。

为了避免麻烦，我们先让 $a$ 变成那个深度更大的结点即可。不影响最终结果。

我们有代码：

if(d[a]<d[b]) swap(a, b);

for(int i=20; i>=0; i--) //2^20足够了。想要省事可以用 log(a) 优化
{
    if(d[f[a][i]] >= d[b]) a = f[a][i];
    //把 a 不断向上跳
    if(a == b) return a;
    //特判。如果两个点相等那么 LCA(a, b) 就是深度小的那个点
}

我们考虑从一个较大的数 $i$ 作为 $2$ 的次幂枚举，如果 $a,b$ 两点的第 $2^i$ 个祖先（即 $f_{a,i}\ \text{和}\ f_{b,i}$ ）不一样，那么就

$a=f_{a,i}\ \ \ \ \ b=f_{b,i}$

也就是 $a,b$ 同时向上跳 $2^i$ 步。

这样，在从大到小枚举所有的 $i$ 之后，当前的 $a',b'$ 必定是 $\text{LCA}(a,b)$ 的左右儿子，那么返回一个 $f_{a',0}\text{或}f_{b',0}$ 即可（即 $a',b'$ 的父亲）。

注意！这里说的都是**从大到小枚举 $2$ 的次幂**，一定要记住，否则这个算法就错了。

我们有求 $\text{LCA}(a,b)$ 的代码：

int LCA(int a, int b)
{
    if(d[a]<d[b]) swap(a, b);

    for(int i=20; i>=0; i--)
    {
        if(d[f[a][i]] >= d[b]) a = f[a][i];
        if(a == b) return a;
    }

    for(int i=20; i>=0; i--)
        if(f[a][i] != f[b][i])
            a = f[a][i], b = f[b][i];

    return f[a][0];
    //此处亦可返回 f[b][0] ，答案都一样
}

~~是不是很简单呢。~~

考虑为什么倍增 LCA 不会超时。

就像上面说的一样，暴力做法是一步一步往上跳，相当于每次只跳 $2^0$ 步。