自动搬运

查看原文

来自洛谷，原作者为

	kradcigam 永不放弃之心，将成为贯穿逆境之光！

搬运于2025-08-24 23:15:53，当前版本为作者最后更新于2025-05-12 13:56:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

感谢 @_LHF_ 同学将本题的空间复杂度优化到了 $O(n)$，加强版链接：https://www.luogu.com.cn/problem/P11690。

完整的解题报告可以见此处。由于当时命制这道题的时候，分别想到了 $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$，

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

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

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

我们在过程中维护：

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

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

  $G_i$ 表示到 $x$ 的距离 $\ge i$ 的棋子到 $x$ 的距离和。

假设当前在结点 $x$，

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