题解 P5024 【保卫王国 】

· · 题解

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

本题解同样发在 UOJ

算法一

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

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

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

### 算法二 考虑修改的两个点 $a,b$ 构成这条链。 可以把操作看作是：先在这条链伸出去的每棵子树上 DP，最后再在这条链上 DP。 伸出去的子树以及链的中间的点和修改无关，因而可以整合起来高效处理，因为它们的转移是不受影响的；但是 $a$ 和 $b$ 的转移是受影响的，需要单独处理。 因此可以先预处理出每个子树的 DP 值，然后用倍增或树剖维护“从一个点往上按照通用规则 DP 到另一个点的结果”，这样只需要特殊处理修改的点，其他地方只需要直接倍增。 $O(n\log n)$。 ### 算法三 如果不想写倍增，也可以写这样一个算法：把所有的询问放在一起处理。 也就是说，由于每条链中间的 DP 转移全部相同，因而我们可以批量地对所有需要进行这一转移的 DP 进行转移，从而加快速度。 这个算法虽然实现较容易，但理解较为困难，因而不再叙述。 $O(n\log n)$。