高效求解树上最近公共祖先的三种算法解析

核心逻辑与数学原理

最近公共祖先（Lowest Common Ancestor, LCA）定义为：在有根树 $T$ 中，对于任意两点 $u, v$，满足既是 $u$ 的祖先也是 $v$ 的祖先，且深度最大的节点，记为 $\text{LCA}(u, v)$。

NOIP 核心的三种求解范式在时间与空间权衡上各有其数学本质：

1. 倍增法（树上二进制拆分）

基于二进制状态压缩的思想。通过预处理出每个节点的 $2^k$ 级祖先，将线性跳转 $O(N)$ 优化为对数级跳转 $O(\text{log} N)$。

• 数学原理：任何十进制整数（此处指两点间的深度差值）皆可唯一拆分为若干个 $2$ 的幂次之和。利用类似 ST 表的递推结构，可在 $O(\text{log} N)$ 时间内对齐深度并同步向上逼近。

2. Tarjan 算法（离线并查集）

基于深度优先遍历与并查集（Disjoint Set Union, DSU）融合的离线算法。

• 数学原理：在对树进行 DFS 的过程中，任一时刻节点被分为三类：已访问且已回溯完毕（标记为 2）、正在访问的栈中节点及路径上的祖先（标记为 1）、未访问（标记为 0）。当 DFS 正在处理节点 $u$，且有一个离线查询 $(u, v)$，若 $v$ 已经访问完毕（标记为 2），则 $u$ 和 $v$ 的 LCA 必然是当前 $v$ 所在并查集的根节点（该根节点必然是当前执行栈中的某个祖先）。

3. RMQ 转化法（欧拉序 + ST 表）

将树形拓扑结构向线性代数最值问题的无损映射。

• 数学原理：在路径欧拉序中，节点 $u$ 和 $v$ 首次出现的位置分别为 $\text{first}[u]$ 和 $\text{first}[v]$。在欧拉序列的区间 $[\text{first}[u], \text{first}[v]]$ 中，深度最小的那个节点，就是 $\text{LCA}(u, v)$。通过 $O(N \text{log} N)$ 的 ST 表预处理，可实现 $O(1)$ 的在线查询。

状态设计与算法推导

1. 倍增法

定义 $fa[u][k]$ 为节点 $u$ 向上跳 $2^k$ 步所到达的祖先节点；$\text{dep}[u]$ 为节点 $u$ 的深度。

• 状态转移方程：

$$fa[u][k] = fa[fa[u][k-1]][k-1]$$

物理含义：向上跳 $2^k$ 步相当于先向上跳 $2^{k-1}$ 步，再从该位置向上跳 $2^{k-1}$ 步。

• 边界条件：$fa[u][0] = parent$。若跳出根节点，则 $fa[u][k] = 0$。
• 查询算法：

1. 设 $\text{dep}[u] \text{≥} \text{dep}[v]$。利用二进制拆分，将 $u$ 向上提升到与 $v$ 同一深度。
2. 若此时 $u == v$，则 $v$ 即为 LCA。
3. 否则，$u$ 和 $v$ 同时向上尝试跳跃 $2^k$ 步。若 $fa[u][k] \neq fa[v][k]$，则同步更新 $u = fa[u][k], v = fa[v][k]$。
4. 循环结束后，$\text{LCA}(u, v) = fa[u][0]$。

2. RMQ 转化法

定义 $\text{euler}[i]$ 为欧拉序列，$\text{dep\_seq}[i] = \text{dep}[\text{euler}[i]]$ 为该位置对应的深度序列。利用 ST 表维护区间最值：定义 $f[i][k]$ 为深度序列中从位置 $i$ 开始，长度为 $2^k$ 的区间内，深度最小的值所对应的欧拉序索引。

• 状态转移方程：

$$pos\text{_}l = f[i][k-1], \quad pos\text{_}r = f[i + 2^{k-1}][k-1]$$

$$f[i][k] = \text{dep\_seq}[pos\text{_}l] < \text{dep\_seq}[pos\text{_}r] ? pos\text{_}l : pos\text{_}r$$

C++ 标准源码（倍增法工业级模板）

#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 500005;
const int MAXLOG = 21; // 2^20 > 500000，确保覆盖深度

std::vector<int> adj[MAXN];
int dep[MAXN];
int fa[MAXN][MAXLOG];

// 预处理深度与 2^0 级祖先
void dfs_lca(int u, int p) {
    dep[u] = dep[p] + 1;
    fa[u][0] = p;

    // 动态规划状态转移，预处理倍增数组
    for (int k = 1; k < MAXLOG; ++k) {
        if (fa[u][k - 1] != 0) {
            fa[u][k] = fa[fa[u][k - 1]][k - 1];
        } else {
            fa[u][k] = 0; // 致命低级错误防范：跳出根节点必须置 0
        }
    }

    for (size_t i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i];
        if (v == p) continue;
        dfs_lca(v, u);
    }
}

// 在线查询 LCA
int query_lca(int u, int v) {
    if (dep[u] < dep[v]) std::swap(u, v); // 始终保证 u 比 v 深

    // 第一阶段：将 u 提升到与 v 同等深度
    for (int k = MAXLOG - 1; k >= 0; --k) {
        if (dep[fa[u][k]] >= dep[v]) {
            u = fa[u][k];
        }
    }

    if (u == v) return u;

    // 第二阶段：同步向上逼近
    for (int k = MAXLOG - 1; k >= 0; --k) {
        if (fa[u][k] != fa[v][k]) { // 关键：只有两者的祖先不同时才跳转
            u = fa[u][k];
            v = fa[v][k];
        }
    }

    // 最终停在 LCA 的下一层，返回父节点即可
    return fa[u][0];
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, root;
    if (!(std::cin >> n >> m >> root)) return 0;

    for (int i = 1; i < n; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 初始化根节点深度的物理边界，传 0 作为根的父节点
    dep[0] = 0;
    dfs_lca(root, 0);

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        std::cout << query_lca(u, v) << "\n";
    }

    return 0;
}

NOIP 实战避坑指南

1. 倍增法提升深度时循环顺序逆反： 在对齐深度或双指针同步向上逼近时，二进制循环必须从大到小（即 for (int k = MAXLOG - 1; k >= 0; --k)）。如果写成从小到大循环，贪心策略失效，无法正确组装出目标深度差值，导致查询结果退化或指针死锁。
2. 根节点父节点未做越界保护： 若没有在 dfs_lca 中正确处理 fa[u][k - 1] == 0 的边界，导致 fa[u][k] 访问了 fa[0][k - 1]。如果 dep[0] 或 fa[0] 数组未清零或包含了脏数据，整个倍增链条将发生拓扑崩塌，引发死循环或错误的祖先定位。

经典 NOIP/洛谷 真题

1. 洛谷 P1967 [NOIP2013 提高组] 货车运输

• 题意描述： 给定一个 $N$ 个点 $M$ 条边的无向图，每条边有一个最大载重限制。有 $Q$ 个询问，每次输入两个点 $x$ 和 $y$，求从 $x$ 到 $y$ 的所有路径中，路径上最小边权的最大值是多少。如果无法到达则输出 -1。
• 问题本质与核心思路： 最大生成树 + 树上倍增。 根据最大生成树（Kruskal）性质，任意两点间“最小边权最大”的路径必然在最大生成树上。建好树后，问题转化为求树上 $x$ 到 $y$ 路径上的最小边权。利用倍增法求解 LCA，并在倍增状态中加入一个属性：定义 $w[u][k]$ 为节点 $u$ 向上跳 $2^k$ 步过程中经过的最短边权。状态转移方程同构递推：$w[u][k] = \text{min}(w[u][k-1], w[fa[u][k-1]][k-1])$。在求解 LCA 的两个阶段同步更新载重最小值，时间复杂度 $O((M + Q) \text{log} N)$。

2. 洛谷 P3128 [USACO15JAN] Max Flow P

• 题意描述： 给定一棵包含 $N$ 个节点的树和 $K$ 条运输路径。每条路径 $(u, v)$ 会让路径上所有节点（包括端点）的压力值加 $1$。求在所有运输完成后，树上压力最大的节点的压力值。
• 问题本质与核心思路： 树上点差分。 若对每条路径使用树剖或暴力修改，复杂度不可接受。由于是静态全量统计，可引入树上差分。对于路径 $(u, v)$，利用倍增法求出 $a = \text{LCA}(u, v)$。在差分数组 diff 上执行：

$$\text{diff}[u] \leftarrow \text{diff}[u] + 1, \quad \text{diff}[v] \leftarrow \text{diff}[v] + 1$$

$$\text{diff}[a] \leftarrow \text{diff}[a] - 1, \quad \text{diff}[fa[a][0]] \leftarrow \text{diff}[fa[a][0]] - 1$$

修改完成后，运行一次自底向上的 DFS 回溯，各节点的真实压力值即为其子树的差分值之和。总时间复杂度 $O((N + K) \text{log} N)$。