题解 【P7897 [Ynoi2006] spxmcq】

· · 题解

其实挺套路的。

我们首先考虑设当前的询问是 x，然后考虑 O(nm) 的暴力 DP。

发现式子是：

f_u=a_u+x+\sum_{u\to v}\max(f_v, 0)

然后我们考虑怎么算这个东西。

我们考虑建一个森林。对于每一个原树的状态，只对所有满足 f_u \ge 0 的点连一条连向原树上父亲的边，那么就能得到一个森林。显然我们只会不断加边。

然后我们意识到如果我们对这个森林跑刚才的 DP，只需要这样：

f_u=a_u+x+\sum_{u\to v} f_v

注意到这个式子就是加上 x 之后的子树和，其实就是这个子树不加 x 的子树和加上 x 乘上子树大小。那么我们只要能够对于每一个 x 快速求出子树形态，基本上就能快速处理这个东西了。

然后我们考虑把 x 递增排序，那么显然 f_u 也是单调递增的。

因此对于每一个点 \max(f_v, 0) 是取 f_v 还是 0 显然只会变化一次。

因此每一条边只会从 断 变成 连 一次，只要能够快速找到所有这样的边即可。

考虑维护一个 std::set，每一个点对应一个权值 val 表示 x\ge val 时这个点是取 f_u 的，

然后考虑这个 val 是什么，我们显然可以列一个方程：

sz\times val+sum\ge0

因此

val= \lceil\frac{sum}{sz}\rceil

其中 sz, sum 分别表示子树大小和子树和。

考虑我们每连一条边，都只会改变集合中 \mathcal{O}(1) 个元素的这两个值，而且在原树上相当于一个链修改。

因此我们再加上一个单点修改区间查询的数据结构就行了。

得到复杂度 \mathcal{O}((n+m)\log n)。

有没有更优做法我就不知道了，但我确实是压线过去的。