查看原题'" class='mdui-btn mdui-btn-raised mdui-ripple'>点击加载点击跳转解法一最小权覆盖集 = 全集 - 最大权独立集动态 dp 只要把强制取点,不取点可以分别把点的权值改为正无穷与负无穷解法二倍增/树链剖分+树形 dp 每次修改的两个点$a,b$构成一条链可以链上连接的子树与链中间的点的结果不受修改影响,只有$a,b$的转移受影响,需要单独处理那么我们可以把子树的答案都预处理出来,链中间部分可以用倍增或树链剖分维护这样只需要处理$a,b$设$f(i,0/1)$表示$i$选/不选,以$i$为根的子树的最小代价,$g(i,0/1)$表示整棵树除了以……