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

ToBeDetermined · 2026-02-22 21:24:56 · 题解

没场切，遂写题解。

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

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

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

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

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

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

• 重心是离 u 最近的满足子树权值和 \ge \frac s 2 的祖先。显然，可以参考方法 1。

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