最近公共祖先 (LCA, Lowest Common Ancestor)：树中两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。

朴素算法

预处理

记录树中每个节点 $i$ 的深度 $dep_i$ 和父节点 $fa_i$。可以在 DFS 遍历整棵树的同时完成这个预处理。

时间复杂度：$O(V)$

求解

给出要求解 LCA 的两个节点 $a,b$，不妨设 $dep_a\geq dep_b$.

首先，较深的节点 $a$ 需要先向上跳到和 $b$ 一样的深度：

while (dep[a] > dep[b])
    a = fa[a];

跳到一样的深度后，如果 $a=b$，则说明二者的 LCA 就是 $b$，输出 $b$ 结束算法。

如果 $a\neq b$，则说明二者的 LCA 还在上层，接下来 $a$ 和 $b$ 一起往上一层层跳，直到找到公共祖先。

while (a != b)
    a = fa[a], b = fa[b];

时间复杂度：$O(d)$，其中 $d$ 为树的深度。对于一个随机树，它的平均深度 $d=\log V$，那么时间复杂度为 $O(\log V)$.

倍增算法

上面朴素算法最大的问题就是跳得太慢了，每次都是一层一层得往上找。我们其实可以用倍增来找，即每次向上跳 $2^n$ 层。

以下面这个树作为例子，要求 $14$ 和 $15$ 的 LCA：

1 |        1
  |       / \
2 |     2     3
  |    /|\   / \
3 |   5 6 7 8   9
  |  / \
4 | 10  11
  | |   | 
5 | 12  13
  | |   |
6 | 14  15

• 找 $14$ 和 $15$ 往上 $8$ 层的祖先，发现二者祖先已经超出根节点了，我们看作相同，缩小距离继续。
• 找 $14$ 和 $15$ 往上 $4$ 层的祖先，发现二者都为 $2$，祖先相同，缩小距离继续。
• 找 $14$ 和 $15$ 往上 $2$ 层的祖先，发现二者为 $10,11$，祖先不同，向上跳后继续。
• 找 $10$ 和 $11$ 往上 $1$ 层的祖先，发现二者都为 $5$，祖先相同，缩小距离继续。
• 距离缩小到 $0$，结束算法。此时 $a$ 或 $b$ 的上一层祖先便是求出的 LCA.

有一点比较难理解，为啥祖先不同时往上跳，祖先相同时只缩小距离。其实这有点二分的味道：

如下图，假设 $a,b$ 两点的 LCA 为 $11$，那么首先跳 $16$ 发现祖先相同，于是下一步跳 $8$ 发现祖先不同...... 其实就是二分。

1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
=============================================√
=====================x
                      ===========√
                      =====x
                            ==√      

当然，倍增算法首先也要把两个点先跳到一层，跳的方法也是使用倍增来完成。

例如 $a$ 比 $b$ 深 $7$ 层的话，就会跳 $4+2+1$，最后 $a,b$ 到同一层。

预处理

记录树中每个节点 $i$ 的深度 $dep_i$ 和向上跳 $2^j$ 层的父节点 $fa(i,j)$。可以在 DFS 遍历整棵树的同时完成这个预处理。

父节点的维护其实算作一种动态规划，转移方程为：$fa(i,j+1)=fa(fa(i,j),j)$

另外，可以预处理出来所有的 $\lfloor \log_2 x\rfloor+1$，这个是一个常数级别优化。递推方式为：mylog2[i] = mylog2[i - 1] + (1 << mylog2[i - 1] == i);

constexpr int MAXN = 1e6 + 10;
int h[MAXN], e[MAXN], ne[MAXN], idx;
int mylog2[MAXN]; // \lfloor log_{2}{x} \rfloor + 1
int fa[MAXN][30], dep[MAXN];

void init()
{
    memset(h, -1, sizeof(h));
    for (int i = 1; i < MAXN; i++)
        mylog2[i] = mylog2[i - 1] + (1 << mylog2[i - 1] == i);
}

void dfs(int now, int father)
{
    fa[now][0] = father;
    dep[now] = dep[father] + 1;
    for (int i = 0; i < mylog2[dep[now]]; i++)
        fa[now][i + 1] = fa[fa[now][i]][i];
    for (int i = h[now]; i != -1; i = ne[i])
        if (e[i] != father)
            dfs(e[i], now);
}

时间复杂度：$O(V\log d)$，其中 $d$ 为树的深度。

计算

int lca(int a, int b)
{
    if (dep[a] < dep[b])
        swap(a, b); // make a >= b
    while (dep[a] > dep[b])
        a = fa[a][mylog2[dep[a] - dep[b]] - 1];
    if (a == b)
        return a;
    for (int i = mylog2[dep[a]] - 1; i >= 0; i--)
    {
        if (fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return fa[a][0];
}

时间复杂度：$O(\log d)$，其中 $d$ 为树的深度。

树链剖分

预处理时间复杂度：$O(n)$

查询时间复杂度：$O(\log n)$

具体介绍见：树链剖分