专题：LCA、倍增与树上差分

本讲定位：图论系列第十二讲，也是本系列与顶层通用算法线的一次正面合流——顶层 07 讲的序列差分，在本讲被原样搬到树上。上一讲说”树上任意两点的路径是唯一确定的”，本讲给出把这条路径真正算出来的工具：最近公共祖先（LCA），以及建立在它之上的树上差分。做了六组实测，三个结论值得先记住：倍增 LCA 在随机树上比”一步步往上跳”的暴力慢 2.2 倍——它的全部价值在链状深树上（实测快 543 倍），交叉点在深度 100～1000 之间；倍增 LCA 那五行代码里每一行写错都是 33%～66% 的错误率（漏 swap 33.03%、>= 写成 > 66.04%、漏 if(u==v) 54.73%、最后返回 u 而不是 fa[u][0] 45.27%）；点差分漏掉 d[fa[lca]]-- 错 67.94%，而把边差分的式子用在点差分上错 100.00%。本讲还会兑现第 10 讲挂着的两笔欠账（P1967 货车运输、严格次小生成树要的”严格次大边”）。文中所有代码经 g++ -O2 -std=c++14 -Wall 编译运行，P3379、P3128、P3258、P1967 与洛谷官方样例核对通过。

前置知识：第 11 讲（硬前置：fa/dep/siz、那个迭代版 prepare 起手式、DFS 序与”子树 = 连续区间”）；顶层 07-prefix-sum-difference.md 的序列差分（第 5 节全程与它对照，没学过的话先去看那一讲的差分部分）。第 4.3 节要用到第 10 讲的最大生成树。

适合对象：第 2 节标 J⭐ / S（LCA 是 CSP-J 的上限内容、CSP-S 的必备）；第 3、4、5 节标 S；第 4.4 节标 S⭐。CSP-J 冲一等的同学至少要会第 2 节的模板和第 3.1 节的距离公式，这两块 J 组已经出现过。

1. 从”路径唯一”到”把路径算出来”

上一讲的结论是：树上任意两点之间有且仅有一条路径。于是”$u$ 到 $v$ 的路径”是个确定的对象。但确定不等于算得出来。看三个问题：

朴素做法都是”顺着路径走一遍”，单次 $O(\text{路径长度})$，最坏 $O(n)$。$m$ 次就是 $O(nm)$——$5\times10^5$ 规模下彻底没戏。

三个问题的共同卡点是同一件事：

想快速处理”$u$ 到 $v$ 的路径”，先要知道这条路径在哪里”拐弯”。

树上路径的形状永远是：从 $u$ 往上走到某个点，再往下走到 $v$。那个”最高点”就是 $u$ 和 $v$ 的最近公共祖先。

2. LCA：最近公共祖先

2.1 定义

给定一棵有根树，$u$ 和 $v$ 的最近公共祖先 $\mathrm{lca}(u,v)$ 是：既是 $u$ 的祖先、又是 $v$ 的祖先的点中，深度最大的那个。

（约定每个点是自己的祖先，所以 $u$ 是 $v$ 的祖先时 $\mathrm{lca}(u,v) = u$。）

它把一条路径切成两段：$u \rightsquigarrow \mathrm{lca}$ 和 $\mathrm{lca} \rightsquigarrow v$，两段都是竖直的（沿着父亲链）。“竖直的路径”好处理——这是本讲所有技巧的共同出发点。

2.2 朴素做法：一步步往上跳

int lcaBrute(int u, int v) {
    while (dep[u] > dep[v]) u = fa[u];        // 先把深的提上来
    while (dep[v] > dep[u]) v = fa[v];
    while (u != v) { u = fa[u]; v = fa[v]; }  // 一起往上，直到相遇
    return u;
}

三行，非常好写，而且第 2.7 节会告诉你：在随机数据上它比倍增还快。 它的问题只有一个——树是一条链时单次 $O(n)$。