SXOI

经典最大独立集问题可设 \(dp_{u,0/1}\) 表示 \(u\) 为根的子树内，不选/选 \(u\) 的独立集最大权。 本题求方案数，且 \(k\) 这么小，暗示我们将上面状态压到维度，设 \(f_{u,i,j}\) 表示以 \(u\) 为根的子树内，\(dp_{u,0}=i,dp_{u,1} ......

题目分析： 就借助这个题稍微说一下 $dp$ 套 $dp$。 对于 $dp$ 套 $dp$ 其解决的问题是：若给定某一具体情况则答案十分好求，现要求对于所有的情况的答案进行统计。 这类问题我们一般称解决这个具体情况的 $dp$ 为内层 $dp$，而对于所有情况进行统计的 $dp$ 为外层 $dp$。 ......

碎碎念 不会写难题，随简单省选题切一切捏。 注意到，一定是要钦定所有的 nk 种权值之后再去算方案的。 对于最大权独立集，我们可以设。 dp[x][0/1][v] 表示 x 选/不选，其子树内已经选了权值 v 作为其最大独立集的方案数。 就是这个捏。 需要注意的是，如何处理所钦定的 v 统计的方案一 ......