P9336 [Ynoi2001] 梦想歌 题解

· · 题解

本文为 zhouhuanyi做法 更详细的说明。

暴力

不难发现，暴力就是按题意模拟。我们可以对于每次查询操作重新维护所查询子树内的所有集合。时间复杂度 O(qn \log n)。

转化

思考一番后，我们会发现暴力的问题在于：原树中，题目中求的 「合并入另外一个集合」操作的节点 的位置是不确定的。这导致我们无法快速找到和维护这个点。

考虑根据合并的过程重新建一棵树。对于两个待合并的子树 x 和 y，我们新建一个权值为 0 的虚点 \alpha，然后 x 和 y 分别成为 \alpha 的左右儿子。

不难发现，建新树的过程根 Kruscal 重构树很类似。新树也有跟其类似的性质，比如它是一棵二叉树。特别地，除叶节点以外的点权值都为 0。

我们思考原题中的操作在新树上的对应。我们规定一个节点的 重儿子 为子树权值和最大的儿子。不难发现修改操作即为修改一个叶节点的权值，查询操作即为查询一个节点所在重链的底端权值。

在这样的转化下，我们便有了一个复杂度更优的做法：每次查询重新对子树做重链剖分，复杂度 O(qn)。

正解

考虑维护每个点所在的重链底。我们希望有一种向下跳的方式，能从子树根快速跳到重链底。这启示我们考虑 树的重心。在下文中，重心 的定义为，删除该点后使剩余连通块权值和最大值最小的点。

引理1：新树的一个子树的重心一定在该子树的重链上。

证明：由于非叶子节点的权值都为 0，如果重心不在重链上，那么将其父亲的重儿子作为中心显然更优。

于是我们从子树的根开始不断跳到当前子树的重心，便一定能跳到重链底。若重心恰为当前点，则说明左右两子树权值和相等。根据原题中 同时，若两个集合的权值和相同，以集合中最小节点深度为第二关键字进行比较（深度大的向深度小的合并）。 的要求，直接走到原树中最小深度较小的子树即可。根据重心的定义，我们每次跳跃都会使当前子树权值和至少减半，因此我们单次查询最多跳跃 O(\log \sum a_i) 次。

现在最大的问题变成了如何快速找到当前子树的重心。

引理2：重心的子树权值和至少为当前子树权值和的一半。

证明：根据重心的定义，如果其不满足这个条件，那么把重心换成它的父亲一定不劣。

引理3：将子树内所有节点权值按 dfs 序组成一个序列，则该序列的 带权中位数 所对应的点一定在重心的子树内。

带权中位数 的定义为：对于一个长度为 n 的非负整数序列 \{a\}，则满足 2 \times \sum\limits_{i = 1}^{k - 1}a_i < \sum\limits_{i = 1}^{n}a_i 且 2 \times \sum\limits_{i = 1}^{k}a_i \ge \sum\limits_{i = 1}^{n}a_i 的位置 k 为 \{a\} 的 带权中位数 所在位置。

证明：根据引理2，重心的子树权值和至少为当前子树权值和的一半，此外重心的子树 dfn 序是一段连续的区间。如果带权中位数的对应点不在重心的子树内，就与带权中位数的定义矛盾。

进一步地，由于非叶子节点权值都为 0，显然带权中位数对应点一定为一个叶子节点。于是我们从这个叶子节点倍增地往上跳，则一定能跳到重心。

由于有单点修改操作，我们可以用树状数组维护子树权值和。修改操作即为在对应 dfn 位置单点改；找带权中位数可以在子树对应 dfn 区间内二分，然后每次区间查询权值和；判定重心也可以之间求子树 dfn 区间的权值和。由于要跳 O(\log \sum a_i) 次重心，每次二分和倍增复杂度为 O(\log n)，树状数组查询需要 O(\log n)，所以单次查询操作的时间复杂度为 O(\log^2 n \log \sum a_i)，为复杂度瓶颈。

至此，我们在 O(n \log n + q \log^2 n \log \sum a_i) 时间复杂度内解决了本题。时间较卡，实现时须尽量减少树状数组查询的次数。