自动搬运

查看原文

来自洛谷，原作者为

	DPair その真っ白な心に、これからたくさんの思い出を。未来を想い、少女は少年に名を赠る。

搬运于2025-08-24 22:34:03，当前版本为作者最后更新于2021-10-12 16:08:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

其实挺套路的。

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

发现式子是：

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

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

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

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

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

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

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

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

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

因此

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

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

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

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

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