经典最大独立集问题可设 \(dp_{u,0/1}\) 表示 \(u\) 为根的子树内，不选/选 \(u\) 的独立集最大权。
本题求方案数，且 \(k\) 这么小，暗示我们将上面状态压到维度，设 \(f_{u,i,j}\) 表示以 \(u\) 为根的子树内，\(dp_{u,0}=i,dp_{u,1}=j\) 时的方案数，此时状态数 \(O(n^3k^2)\)，转移总复杂度 \(O(n^4k^4)\)。
若要优化我们显然需要缩减状态数，而 dp 套 dp 想要缩减状态数就要从内层 dp 入手。不妨改写内层 dp，设 \(dp'_{u,0/1}\) 表示以 \(u\) 为根的子树内，强制/不强制不选 \(u\) 时的独立集最大权，即 \(dp'_{u,0}=dp_{u,0},dp'_{u,1}=\max(dp_{u,0},dp_{u,1})\)。此时内层 dp 仍然可以转移，且有：
- \(dp'_{u,0}\le dp'_{u,1}\)
- \(dp'_{u,1}-dp'_{u,0}\le a_u\le k\)
此时我们可以设新外层 dp \(g_{u,i,j}\) 表示以 \(u\) 为根的子树内，\(dp'_{u,0}=i,dp'_{u,1}=i+j\) 的方案数，此时状态数少 \(n\)，转移总复杂度可以达到 \(O(n^2k^4)\)。加上判一些 \(0\) 的转移剪枝即可跑的飞快。
dp 套 dp 的状态优化要从内层 dp 下手，通过改写内层 dp 简化状态信息。
标签：状态,le,SDOI,SXOI2022,P8352,内层,为根,dp,子树内 From： https://www.cnblogs.com/ydtz/p/17793945.html