自动搬运

查看原文

来自洛谷，原作者为

	immortalCO **

搬运于2025-08-24 22:06:18，当前版本为作者最后更新于2018-11-12 11:25:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

利益无关：猫锟不是本题的命题猫。

本题解同样发在 UOJ

算法一

最小权覆盖集 = 全集 - 最大权独立集

强制取点、不取点可以使用把权值改成正无穷或负无穷实现。

接下来就是 https://www.luogu.org/problemnew/show/P4719 了。

$O(n\log n)$。

算法二

考虑修改的两个点 $a,b$ 构成这条链。

可以把操作看作是：先在这条链伸出去的每棵子树上 DP，最后再在这条链上 DP。

伸出去的子树以及链的中间的点和修改无关，因而可以整合起来高效处理，因为它们的转移是不受影响的；但是 $a$ 和 $b$ 的转移是受影响的，需要单独处理。

因此可以先预处理出每个子树的 DP 值，然后用倍增或树剖维护“从一个点往上按照通用规则 DP 到另一个点的结果”，这样只需要特殊处理修改的点，其他地方只需要直接倍增。

$O(n\log n)$。

算法三

如果不想写倍增，也可以写这样一个算法：把所有的询问放在一起处理。

也就是说，由于每条链中间的 DP 转移全部相同，因而我们可以批量地对所有需要进行这一转移的 DP 进行转移，从而加快速度。

这个算法虽然实现较容易，但理解较为困难，因而不再叙述。

$O(n\log n)$。