树链剖分

第一次看到树链剖分（简称树剖）可能觉得它非常的深奥，但其实树剖的原理非常简单，下面先说树剖大概的实现思路和解决题型。

概览

其实树剖就是把一棵树分成若干条链，使得每个点都出现在了刚好一条链上。

并且，我们称在某条链上的边为“重（zhòng）边”，不在任何一条链上的边为“轻边”。

然后，我们按某种规则去DFS，求出新的DFS序，然后解决对树上路径询问的问题。

而且，通过合理的设计每条边的轻重，可以把复杂度控制在 $O(\log n)$ 级别。

解决题型

上面也提到了，树剖就是用来解决对树上路径进行询问的问题的算法，当然也可以解决对子树询问的问题，不过属于大材小用了。

此外，树剖属于工具类算法，所以往往会配合树状数组、线段树、分块等算法出现。

我把算法分为了两类，“材料类算法”和“工具类算法”，其中：

• 材料类算法可以单独考，比如：
  • 数论
  • 推公式
  • DP
  • 树状数组
  • 线段树
  • …
• 工具类算法里面必须要套材料类算法才能考出来，比如：
  • 二分
  • 01分数规划（二分的一个分支）
  • CDQ分治（需要配合树状数组）
  • 整体二分（需要配合树状数组）
  • 树剖（这里讲的）
  • …

往往一些较难的题目，都是要用较难的材料类算法（比如DP），或者工具类算法配合材料类算法才能解决的题目。

而对于后者，难度会更大一些，因为后者的关键在于转化后使用工具类算法解决。

算法实现

下面说一下树剖的实现。

两遍DFS

我们考虑DFS，当递归到点 $x$ 的时候，找到 $x$ 的儿子中，子树大小最大的那个儿子 $to$。

然后，我们把 $x \to to$ 这条边设为重边，其他边设为轻边。

得到每条边的轻重后，我们再做一遍DFS。

而这一遍DFS是为了找到DFS序。

而且，DFS序有一个要求，我们要先遍历有重边连接的儿子。

这样的话，对于任意一条树上的链，链上所有点的DFS序连续，而且是由深度从浅到深依次递增。

同时，我们还要求出，从一个点开始，不经过任何轻边，最多到哪个点。

解决询问

而对于一次路径上某值的询问，我们可以把这个路径拆成若干条链。

可以证明链数不超过 $O(\log n)$，这一点会在下面“复杂度证明”中证明。

而这些拆出的链，都是原树中的链的“子集”（一条链 $L_1$ 是另外一条链 $L_2$ 的子集，有且仅当 $L_1$ 中的点，$L_2$ 中也有，边同理）。

所以，可以把一条路径，拆成最多 $O(\log n)$ 个DFS序区间。

既然如此，我们就可以拿DFS序作为下标，用数据结构维护题目中的信息，询问就是区间查询。

当然，很多时候都有修改，所以一般都是用线段树维护。

复杂度证明

首先，对于任意一个点 $x$，它最多只有一个子节点 $to$（当然，也可能没有），满足 $sz_{to} \geq sz_x \div 2$。

由于我们选择的是子树大小最大的子节点，让该子节点为“重子节点”。

所以，其他“轻子节点”的大小一定不超过 $sz_x \div 2$，显然。

也就是说，如果一个点 $x$ 到其父亲 $fa$ 之间的边是轻边，那么 $sz_{fa} \geq sz_x \times 2$ 一定满足，显然。

而由于 $sz$ 值最多为 $n$，所以从一条路径 $(x,y)$ 的某一端点，走到 $\text{lca}$，最多只会经过 $\log n$ 个重链。

所以单次询问最多分成 $O(\log n)$ 个重链。

总复杂度在 $O(q \log n) \sim O(q \log^3 n)$ 内不等，依据题目和实现决定。