P15407 [NOISG 2026 Prelim] 米浴的数据结构课 题解

没场切，遂写题解。

话说我不是十几天前才做过 P3345 吗，我怎么没场切这题。/ll

设点权和为 。求动态重心主要有以下三种方法：

1. 重心是 DFS 序最大的、满足子树权值和 的点。此方法需要使用线段树维护区间子树权值和最大值。
2. 在 DFS 序上，设第一个权值的前缀和 的点是 ，那么 在重心的子树中，也即重心是 的祖先，且是离 最近的满足子树权值和 的祖先。此方法需要使用线段树维护区间权值和与树上倍增。我太菜了之前不会。/ll
3. 点分树。我太菜了不会。/ll

在本题中，因为有链加与子树加，所以难以维护区间子树权值和最大值，无法使用方法 1。于是使用方法 2 即可。

具体地，用树剖 + 线段树维护当前每个点的点权与区间和，那么容易通过线段树二分求出 。求出 之后，利用倍增找到 祖先中第一个权值 的点即可。时间复杂度 。

这里还是证明一下两个结论。

• 在重心的子树中。因为重心的子树权值和显然 ，所以对于所有 子树权值和 的点（即可能成为重心的点），每个点的子树的 DFS 序一定包含 。
• 重心是离 最近的满足子树权值和 的祖先。显然，可以参考方法 1。

代码等这题有数据了再放。