树上距离 · 虚树 · 树链剖分

这套地基撑起了什么

前面五页解决的是两个具体问题。本页看它们撑起了什么：一旦「问两点的 LCA」变得便宜，一批原本要 $O(n)$ 的树上操作都降到了 $O(\log n)$ 甚至 $O(1)$ 。

1 · 树上距离与路径上的第 k 个点

无权树上两点的距离是路径经过的边数。有了 LCA，它是一个减法：

$\text{dist}(u, v) = \text{depth}[u] + \text{depth}[v] - 2\,\text{depth}[\text{LCA}(u, v)]$

两条向上的路段在 LCA 处汇合。LCA 之上到根的那一截被两个深度各算了一遍，减两倍恰好抵消。带边权时把 $\text{depth}$ 换成「到根的权和」，公式一字不改。

路径上第 $k$ 个点也不必遍历。设上行段长 $d_u = \text{depth}[u] - \text{depth}[\text{LCA}]$ ： $k \le d_u$ 时答案是 $u$ 的第 $k$ 级祖先，否则是 $v$ 的第 $\text{dist} - k$ 级祖先。两种情形都是一次 kthAncestor， $O(\log n)$ 。

图 1-1 · 树上距离的分解与路径上第

k

个点的定位。可换两个端点并拖动

k

观察落点在上行段与下行段之间切换。

2 · 虚树

一类常见需求是：给一批关键点，做一轮只与这些点有关的树上 DP；而这样的询问有很多轮，每轮的关键点数 $k$ 都远小于 $n$ 。逐轮跑整棵树是 $O(nq)$ ，不可接受。

虚树（virtual tree）把每一轮压缩成一棵只有 $O(k)$ 个节点的树：保留全部关键点，再补上「按 DFS 进入时刻排序后相邻两点的 LCA」，其余节点全部压掉，被压掉的一段合成一条带权边。

节点数不超过 $2k - 1$ ： $k$ 个关键点，加上至多 $k-1$ 个补进来的 LCA。 $n = 100000$ 的随机树上实测（每个 $k$ 取 200 组随机关键点）， $k = 5$ 时平均 7.8 个节点、最大 9，正好顶到上界 9； $k = 10$ 时平均 15.8、最大 19，也顶到了上界； $k = 200$ 时平均 328.9、最大 342，离上界 399 还差一截。上界在 $k$ 小时是紧的， $k$ 大起来就松了——关键点一多，随机取到的点更容易共享祖先，补进来的 LCA 就重复了。

图 2-1 · 关键点集合决定的虚树：上方是原树与被保留的节点，下方是压缩后的树，边上标着被压掉的长度。可点按钮增删关键点。

构造只用两样东西： $\text{tin}$ 排序，以及 $k-1$ 次 LCA 查询。前者一次 DFS 就有，后者由前面几页给出。每轮 $O(k \log k)$ ，与 $n$ 脱钩。

注 · 补进来的 LCA 只需取相邻两点的，不必两两都取。理由是 tin 序下，任意两个关键点的 LCA 一定等于它们之间某一对相邻关键点的 LCA——这一条把补点数从 $O(k^2)$ 压到 $O(k)$ ，是整个构造能成立的关键。本系列的测试把它写成了可执行断言：虚树上关键点两两求 LCA 的结果与原树逐个相同。

3 · 两个更远的出口

树链剖分（heavy-light decomposition）把树拆成若干条链，使得任意一条根到叶的路径至多跨 $O(\log n)$ 条链。它同样能回答 LCA，但它真正解决的是更难的问题：路径上的区间修改与区间查询。每条链上挂一棵线段树，路径查询拆成 $O(\log n)$ 段链上区间，每段再花 $O(\log n)$ ，总计 $O(\log^2 n)$ 。

本系列的方法对此无能为力：sparse table 与欧拉序都建立在「树不再改变」之上。要修改就得回到线段树那一侧，树链剖分正是把两者接起来的桥。

另一个出口是区间最值本身的题型。「区间内的最大值出现在哪」这个问题一旦是常数级的，一批扫描类算法就有了新解法：区间最值的分治（每次取最小值把区间劈开，得到的就是笛卡尔树的形状）、最长公共前缀查询（后缀数组的 height 数组上做 RMQ）、二维问题降维后的行内最值。共同的模式是把一个看似要遍历的量，换成一次对静态结构的查询。

树上 DP 与本系列的关系值得单独说一句。树形 DP 处理的是「每个节点的答案由孩子的答案合成」，一次后序遍历解决，用不上 LCA。两者的分工是：树形 DP 算的是子树内的量，LCA 算的是两点之间的关系。虚树是它们的交点——先用 LCA 把树压小，再在小树上跑树形 DP。

4 · 参考文献

Bender, M. A., & Farach-Colton, M. (2000). The LCA problem revisited. In LATIN 2000: Theoretical Informatics (pp. 88–94). Springer.
Sleator, D. D., & Tarjan, R. E. (1983). A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3), 362–391.
Kasai, T., Lee, G., Arimura, H., Arikawa, S., & Park, K. (2001). Linear-time longest-common-prefix computation in suffix arrays and its applications. In Combinatorial Pattern Matching (pp. 181–192). Springer.
cp-algorithms. Heavy-light decomposition. https://cp-algorithms.com/graph/hld.html