• 引子
• 从 k 级祖先谈起
• 长链剖分优化 dp

引子#

我们对树上的节点 定义高度函数 , 满足如果 是叶子, 那么 , 否则 .

长链剖分是一种链剖分, 每个点的重儿子被定义为其子节点中 最大的那个 (有多个则任选一个). 轻子节点被定义为剩余的子结点. 从这个结点到重子节点的边被定义为重边. 从这个节点到轻子节点的边被定义为轻边.

若干条首尾衔接的重边被定义为重链. 一个没有重边连向它的节点也是一条重链(长度为 1 的). 称一条重链中深度最小的点是这个重链的顶点.

从 k 级祖先谈起#

1. 一条重链的长度就是其顶点 的

由于重儿子是子节点中 最大的那个, 所有必然有若 是 的重儿子, 则 .

1. 一个节点 的 级祖先 所在的重链的长度一定不小于 .

由 是 的 级祖先, 必然有 .
不妨设 所在重链的顶点为 , 必然有重链长度等于 .

对于每条重链的顶点, 我们记录两个数组 . 其中 表示该节点的 级祖先在哪条重链(只记录到该条重链长度), 储存从这个节点开始的重链中的所有节点. 对于重链中的每个点我们记录 表示 所在重链的顶点. 对于每个节点, 记录 代表节点 的 级祖先, 代表其深度.

对于节点 的 级祖先这一询问, 我们首先找到 使得 , 然后找到 的 级祖先所在重链的顶点, 记作 . 分类讨论: 若 , 那么 必然在 所在的重链中, 查一遍 即可.

否则我们在 中查到 的 级祖先所在的重链. 具体来说, 就是 . 由第二条性质, 这是合法的. 然后在那条重链的顶点的 中查询即可.

长链剖分优化 dp#

#

给定 个节点的树, 设 为 子树中到 距离为 的节点数量.

对于树上的每个点 , 求一个最小的 , 使得 是 中最大的.

对于 有转移:

$$d(u, k) = \sum\limits_{v\in son(u)} d(v, k-1)$$

且只有 有值.

对树长链剖分, 我们发现我们可以把全部信息记录在重链的顶点上来优化掉第一维. 但是其实我们不需要显式的优化掉第一维, 只需要对于每个节点开一个指针, 然后只给重链的顶点开空间, 其他重链上的点沿用那个顶点的空间即可. 时空复杂度均为 , 其中 是所有重链顶点构成的集合. 由前述的性质 1 可以知道时空复杂度均为 .

BZOJ#4543 Hotel 加强版 Hotel.cpp

Luogu#3899 谈笑风生 谈笑风生.cpp