树链剖分 I
摘要：本文介绍了树链剖分并给出若干例题的解法。
关键词：数据结构 树论 树链剖分 线段树
记号与定义
本博客中：
- 树是一个 \(n\) 个点 \(n-1\) 条边的无向连通图。
- 定义 \(u\) 与 \(v\) 相邻为 \(u\) 与 \(v\) 有边。
- 记一条从 \(u\) 到 \(v\) 的无权边为 \((u,v)\)。
- 记一条从 \(u\) 到 \(v\) 的权为 \(w\) 边为 \((u,v,w)\)。
- 定义对于一个有根树，点的深度为其到根节点的距离。
- 定义对于一个树，树的大小为树的节点个数。
- 定义树上两个点的距离为树上两个点的唯一路径经过的边个数，\(u\) 与 \(v\) 的距离记为 \(\text{dis}(u,v)\)。
- 定义 \(u\) 是 \(v\) 的父亲，当且仅当在有根树中，\(u\) 是 \(v\) 的父亲的充分必要条件是满足 \(d_v=d_u+1\) 且 \(v\) 与 \(u\) 相邻。
- 定义 \(u\) 是 \(v\) 的祖先为，通过不断的让 \(v\) 等于自身的父亲，可以让 \(u=v\)。特别地，\(u\) 是 \(u\) 的祖先。
- 若 \(u\) 是 \(v\) 的后代，则 \(v\) 是 \(u\) 的祖先。
- 定义 \(u\) 的子树为所有 \(v\)，且 \(u\) 是 \(v\) 的祖先的点与除了 \(u\) 以外的 \(v\) 与其父亲的边构成的树。
- 定义 \(u\) 是 \(v\) 的祖先，当且仅当 \(u\) 和 \(v\) 的父亲相同。
- 若 \(w\) 是 \(u,v\) 的祖先，则 \(w\) 是 \(u\) 和 \(v\) 的公共祖先。特别地，所有 \(u\) 和 \(v\) 的祖先中深度最大的是 \(u\) 与 \(v\) 的最近公共祖先，若 \(w\) 是 \(u\) 和 \(v\) 的最近公共祖先，记 \(\text{LCA}(u,v)=w\)。
算法
引入
我们知道维护序列上的很多信息可以使用线段树，比如区间加与区间求和等。
当序列问题转化到树的路径上时，考虑以下题目：
- 树上有 \(n\) 个点，每个点的初始点权均为 \(0\)。
- 操作：对于 \(u\) 与 \(v\) 的路径，每个点的点权加 \(w\)。
- 询问：求 \(u\) 到 \(v\) 的路径上的点权和。
剖树为链
我们思考，我们是否可以把树的问题转化到序列上，序列上的解法是已知的线段树。
我们发现对于一棵树，链是可以看作一个序列进行操作的，这启发我们将树转化为链。实际上，最朴素的做法即为将树剖成了 \(n\) 个长度为 \(1\) 的链，时间复杂度 \(O(qn)\)。
我们可以一次性对于单链上实现 \(O(\log n)\) 的复杂度，这启发我们把树剖分成尽可能少的链。
剖分方法
树链剖分有很多种剖分方法，注意到链的个数等于链的顶端的点的个数。因此我们要让点尽可能地被加进里。贪心地，我们把 \(u\) 的儿子中子树大小最大的加入到 \(u\) 所在的链中。其他的儿子均作为新的链顶端。我们将这种链剖分方法称为重链剖分。