题解：P11690 [Ynoi Hard Round 2025] 《十字神名的预言者》理解（色彩）

kradcigam · 2025-02-20 15:24:48 · 题解

本题是笔者今年的集训队互测试题。

起初是 lxl 认为这道题很有价值，是一道不同寻常的数据结构题，于是询问我是否能加入 Ynoi Hard Round 2025。本着希望能有更多的人做到我的题目，于是我同意了。同时也非常遗憾，没有任何选手能在集训队互测赛时写出什么非平凡的算法。

完整的解题报告可以见此处。由于当时命制这道题的时候，分别想到了 O(n\log^3 n)、O(n\log^2 n)、O(n\log n) 的算法，在解题报告中，算法层层递进，并描述了思考方式，所以可能略显冗长。

这里只描述最终的算法，还是相当简洁的。

基本的贪心

由于 a_i\ge 1，所以我们可以把题目转化成每次选择一个棋子，移到其祖先。

首先，我们有一个暴力的贪心做法。我们 DFS 整棵树，假设当前在结点 x，先对于结点 x 的子树进行贪心的过程，然后再将子树内最深的棋子移到结点 x。

贪心证明

首先，由于操作都是将深度大的棋子，移到深度小的结点上去，所以我们可以将操作按照移到的结点的深度从大到小重排。

于是，我们可以把过程看成 DFS 整棵树，假设当前在结点 x，先对于 x 的子树进行操作，然后进行将子树内的棋子移到当前位置的操作。

假设当前子树内有 k 棵棋子，到 x 的距离按照从小到大排序为 \{a_1,a_2,\cdots,a_k\}。

假设当前可以选择移动一枚棋子到 x，我们可以说明：

选择棋子移动到 x 是不劣的，因为假设选择了第 p 个棋子移动到 x，那么距离序列就变成了 a'=\{0,a_1,a_2,\cdots,a_{p-1},a_{p+1},a_{p+2},\cdots,a_k\}。

注意到，a' 序列能全维偏序 a 序列（这里全维偏序是指所有对应位置的数都有 a'_i\le a_i，下同）。

所以，我们可以说明选择棋子移动到 x 是不劣。
选择第 k 个棋子移动到 x 是不劣的，因为假设选择了第 p\ne k 个棋子移动到 x，那么距离序列就变成了 b=\{0,a_1,a_2,\cdots,a_{p-1},a_{p+1},a_{p+2},\cdots,a_k\}。

假设选择了 a_k 移动到 x，那么距离序列就变成了 b'=\{0,a_1,a_2,\cdots, a_{k-1}\}。

注意到，b' 序列能全维偏序 b 序列。

所以，我们可以说明选择距离最远的棋子移动到 x 是不劣。

维护

我们考虑维护这个过程。我们记 f_{x,i} 表示 x 子树内操作完后到 x 的距离 \ge i 的棋子数量。

记 g_{x,i} 表示 x 子树内操作完后到结点 x 的距离 \ge i 的棋子到 x 的距离和。

我们考虑长链剖分来维护，记结点 x 的长儿子为 \mathrm{hson}_x。

我们先考虑计算 f,g。注意到对于 i\ge \mathrm{height}_x，f_{x,i},g_{x,i}=0，所以我们只需要维护 \mathrm{height}_x 个值。我们可以对每条长链维护 f,g 数组，并且维护当前删除了前 \mathrm{del}_x 大的结点，并维护这些结点到 x 的距离和 \mathrm{sum}_x。具体地，我们对结点 x，

继承 f_{\mathrm{hson}_x} 的状态；
加入轻儿子 y 贡献。由于我们维护的是后缀和，而每次修改是一段前缀，因此我们可以维护；
将前 a_x-b_x 大删除，我们在 f 数组上二分，即可更新 \mathrm{sum}_x。

我们考虑换根计算子树补的信息，这个时候跟先前两道例题的情况大不相同，我们需要新的处理方法。我们考虑把信息拆成轻重子树来处理。

我们考虑在换根的过程中重链剖分维护，记结点 x 的重儿子为 \mathrm{wson}_x。

我们在过程中维护：

到根路径经过的轻结点，它们的父亲的重儿子结点编号集合 S_x；

用数组来维护 F_i 表示到 x 距离 \ge i 的棋子数量。

假设当前在结点 x，

根据 f_x,g_x 回退出 f_{\mathrm{hson}_x},g_{\mathrm{hson}_x}；
我们先将所有轻儿子都加入 F 里面；
对于重儿子：不需要做额外处理；
对于轻儿子：我们先将结点 y 在 f 内的贡献删除，然后再截取重儿子距离 \le \mathrm{size}_y 的部分，对于重儿子 f_{\mathrm{wson}_x} 中 >\mathrm{size}_y 的部分，我们将重儿子的结点编号 \mathrm{wson}_x 加入 S_y 内，并记录 \mathrm{size}_y；
将 f_{\mathrm{hson}_x},g_{\mathrm{hson}_x} 还原成 f_x,g_x。

此外，对于删除距离前 a_x-b_x 大的，注意到我们肯定是依次删 S_x 最早加入的重儿子。于是，我们先判断这个数组能否删空。如果能删空，我们就直接在 S 中删除，否则再二分。这样，我们就只需要进行至多一次二分。

求答案时，我们如果删完 S 后，结点 x 仍有空余位置，我们只需要对数组 f_x 和 F_x 进行二分即可。

如果加入轻儿子时，在已经被删除的地方增加了棋子，则我们可以直接重构 f,g。

时间复杂度 O(n\log n)，空间复杂度 O(n)。