算法进阶 7 分钟阅读

树上算法：树的直径与倍增最近公共祖先 (LCA)

两次 DFS 的几何直觉与树形 DP 对负权边的包容性，配合二进制倍增将树上祖先查询降至对数级。

树的直径：树中最遥远的距离

在无向无环连通图（树）中，两点间路径长度的最大值被称为树的直径（Tree Diameter）。

解法一：两次 DFS / BFS（直觉极佳）

从任意节点 $u$ 出发，运行一次 DFS，找到距离 $u$ 最远的节点 $P$ 。
从节点 $P$ 出发，再运行一次 DFS，找到距离 $P$ 最远的节点 $Q$ 。
节点 $P$ 与 $Q$ 之间的距离即为树的直径。

证明直觉：节点 $P$ 必然是树上某一条直径的端点（反证法易证）。此方法易于输出直径的具体路径，但仅适用于边权全为非负的树。

解法二：树形 DP（普适性最强）

定义 $d_{1} [u]$ 为以 $u$ 为根的子树中， $u$ 向下延伸的最长链长度； $d_{2} [u]$ 为次长链长度（与最长链分属不同子树分支）。转移时，对于 $u$ 的每一个子节点 $v$ ： $d = d_{1} [v] + w (u, v)$ 尝试用 $d$ 更新 $d_{1} [u]$ 与 $d_{2} [u]$ 。穿过节点 $u$ 的最长简单路径长度即为 $d_{1} [u] + d_{2} [u]$ 。遍历所有节点即可得到整棵树的直径。此方法完美支持负权边，时间复杂度严格为 $O (N)$ 。

最近公共祖先（LCA）与二进制倍增

在有根树中，两个节点 $u$ 与 $v$ 的**最近公共祖先（Lowest Common Ancestor, LCA）**是同时为 $u$ 和 $v$ 祖先的节点中深度最大的一个。

如果每次通过父指针一步一步往上跳，最坏单次查询需要 $O (N)$ 。 二进制倍增法利用 $2^{k}$ 的二进制拆分思想，将预处理做到 $O (N lo g N)$ ，单次查询压缩至 $O (lo g N)$ 。

倍增表定义

设 $u p [u] [k]$ 表示节点 $u$ 向上跳 $2^{k}$ 步到达的祖先节点： $u p [u] [k] = u p [u p [u] [k - 1]] [k - 1]$ （即：向上跳 $2^{k}$ 步，相当于先跳 $2^{k - 1}$ 步，再从落点继续跳 $2^{k - 1}$ 步）。

经典查询三步曲

// 预处理 DFS
void dfs(int u, int p, int d) {
    depth[u] = d;
    up[u][0] = p;
    for (int k = 1; k < 20; ++k) {
        up[u][k] = up[up[u][k - 1]][k - 1];
    }
    for (int v : adj[u]) {
        if (v != p) dfs(v, u, d + 1);
    }
}

// 快速查询 LCA(u, v)
int get_lca(int u, int v) {
    // 1. 确保 u 的深度不小于 v
    if (depth[u] < depth[v]) std::swap(u, v);

    // 2. 将 u 提升至与 v 相同的深度
    int diff = depth[u] - depth[v];
    for (int k = 19; k >= 0; --k) {
        if ((diff >> k) & 1) {
            u = up[u][k];
        }
    }
    if (u == v) return u;

    // 3. 同时向上大步倍增跳跃，直到到达 LCA 的正下方
    for (int k = 19; k >= 0; --k) {
        if (up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    }
    return up[u][0]; // 此时两者的父节点即为 LCA
}

结合 LCA，树上任意两点 $(u, v)$ 之间的距离公式可直接写为： $dist (u, v) = depth [u] + depth [v] - 2 \times depth [LCA (u, v)]$ 这是树上路径统计与树上差分算法不可或缺的核心工具。