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

算法一

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

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

接下来就是经典的“动态最大权独立集”了，这题的题解在我之前博客有，洛谷上也可以提交。

$O(n\log n)$。

算法二

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

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

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

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

$O(n\log n)$。

算法三

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

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

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

$O(n\log n)$。

总结

本题的三个做法对应着动态 DP、虚树计算和整体 DP 的思想，体现了三个算法（在一定条件下）的等价性。

动态 DP $\Rightarrow$ 虚树计算：动态维护被修改的点构成的虚树（可能会增加复杂度）；

虚树计算 $\Rightarrow$ 动态 DP：一个一个加入虚树中的点；

动态 DP $\Rightarrow$ 整体 DP：每个修改看作时间的区间，用线段树批量应用修改（不一定可行）；

整体 DP $\Rightarrow$ 动态 DP：一个一个询问进行处理，依次加入对称差（可能会增加复杂度）；

虚树计算 $\Rightarrow$ 整体 DP：按询问分组批量进行；

整体 DP $\Rightarrow$ 虚树计算：通过 整体 DP $\Rightarrow$ 动态 DP $\Rightarrow$ 虚树计算 进行转化（不一定可行）。

可以看出，动态 DP 和整体 DP 具有很强的适用面，都有各自才能解决的问题；而虚树计算的能力则是最弱的，常常可以等复杂度地转化为另外两者（一些例外是需要在虚树上点分治的问题）。