题解：P8294 [省选联考 2022] 最大权独立集问题

居然有个高手 · 2025-03-14 22:59:55 · 题解

超级分讨题吗，哈哈那无敌了。

这种题可以先想一下怎么做多项式复杂度。考虑一个点的度数至多为 3，因此我们可以分类讨论一下有关其交换的顺序。我们发现在交换了 x 与 fa_x 之间的边后 x 子树内为独立问题，可以想到记录子树型状态。

那么我们要记录什么样的状态呢？显然我们关心 x 与 fa_x 交换时的值，同时还有 x 的儿子的交换状态。同时我们又发现，若钦定交换时 d_x = i,d_{fa_x}=j，则在二者交换前，对于 x 子树内，我们只关心让 x 留下的值为 i 时的最小代价；交换后我们只关心 x 目前带的值为 j 时的最小代价。

因此我们可以记录 f_{x,i,0/1/2} 与 g_{x,i,0/1/2} 表示 x 初始时带的权值为 a_i，进行了 0/1/2 状态的交换操作后子树内的最小代价；g_{x,i,0/1/2} 表示 x 进行了 0/1/2 状态的操作后，最终保留权值为 a_i 时子树内的最小代价。（0 表示只换左子树，1 表示只换右子树，2 表示都换）

显然，f_{x,i,op} 状态有效当且仅当 i=x 或 i 在 x 子树外，g_{x,i,op} 状态有效当且仅当 i 在 x 子树内。

开始分讨转移了。对于 f_{x,i,0}，我们枚举此时左子树 ls 的交换情况：

未交换：f_{x,i,0}=a_{ls}+a_i+f_{ls,i,2}。

交换一边（记作 op）：f_{x,i,0}=a_i+\underset j\min\{g_{ls,j,op} + a_j + f_{ls,i,1-op}\}。

交换两边：f_{x,i,0}=a_i + \underset j \min\{g_{ls,j,2}+a_j\}。

容易发现上式中 i,j 不同时出现，因此预处理 g_{ls,j,op}+a_j 的最小值即可。

对于 g_{x,i,0}，我们同样枚举交换情况：

未交换：此时 i=ls，g_{x,i,0}=a_{ls}+a_x+f_{ls,x,2}。

交换一边：g_{x,i,0}=a_i + a_x + g_{ls,i,op} + f_{ls,x,1-op}。

交换两边：g_{x,i,0} = a_i+a_x+g_{ls,i,2}。