P8352 SDOI2022 D2T1 小 N 的独立集 题解

**传送门：**[P8352 [SDOI/SXOI2022] 小 N 的独立集](https://www.luogu.com.cn/problem/P8352) ------------ ### 题意 给定 $n$ 个点的树的形态以及点的权值范围 $k$，对于任意 $i \in [1,kn]$， 求有多少种权值分配方案，使得树的最大权独立集大小为 $i$。 ------------ **1. 经典 dp $(n \le 8)$：** 枚举所有权值分配方案，设 $f_{u,0/1}$ 表示 $u$ 子树中点 $u$ 不选/选的最大独立集然后做经典树上最大权独立集 dp 即可，复杂度 $O(nk^n)$。 **2. dp 套 dp $(n \le 100)$：** 经典 dp 和极小的值域 $(k \le 5)$ 启发我们可以**将 $f_{u,0/1}$ 的值设为状态**。 设 $g_{u,v0,v1}$ 为 $u$ 子树中 $f_{u,0},f_{u,1}$ 分别为 $v0,v1$ 时的方案数。转移时考虑将 $u$ 的一个儿子 $v$ 合并到 $u$ 中，枚举 $i,j,p,q$ 分别作为 $f_{u,0},f_{u,1},f_{v,0},f_{v,1}$，易得转移： $$g'_{u,i+\max(p,q),j+p} \gets g'_{u,i+\max(p,q),j+p}+g_{u,i,j} \times g_{v,p,q}$$ 套用树上背包的复杂度分析可得时间复杂度为 $O(n^4k^4)$，加上判0远远跑不满，能够通过 $n \le 100$。 因为状态转移时是将内层 $f$ 的转移结果作为外层 $g$ 的状态来转移的，所以称作 dp 套 dp。 **3. 状态优化 $(n \le 1000)$：** 上文的 dp 方法复杂度瓶颈在于状态数就已经到达了 $O(n^3k^2)$ 级别，此时可以考虑**简化内层 $f$ 的状态和转移**，考虑另一种树上最大权独立集的 dp 方法：重新定义 $f_{u,0/1}$ 表示 $u$ 子树内是(1)否(0)强制**不选**节点 $u$ 时的最大方案大小，转移显然，如此设便得到了一条重要性质：$0 \le f_{u,0}-f_{u,1} \le val_{u} \le k$（强制不选的答案肯定小于等于无限制的答案，且两者一定不会差出 $u$ 点的权值），此时自然得出 $g_{u,v1,d}$ 表示 $u$ 子树中 $f_{u,0},f_{u,1}$ 分别为 $v1+d,v1$ 时的方案数，依然枚举 $i,j,p,q$，有转移： $$g'_{u,i+p+q,\max(i+j+p,i+p+q)-(i+p+q)} \gets g'_{u,i+p+q,\max(i+j+p,i+p+q)-(i+p+q)}+g_{u,i,j} \times g_{v,p,q}$$ 时间复杂度$O(n^2k^4)$，加判0跑得很快 代码（代码中的 $f$ 数组即为 $g$）： ```cpp //dp套dp #include <bits/stdc++.h> using namespace std; const int MAXN = 1001; const int Mod = 1e9+7; int n, k, siz[MAXN]; int f[MAXN][MAXN * 5][6], t[MAXN * 5][6]; int head[MAXN], edge_num; struct edge { int nxt, to; } T[MAXN * 2]; inline void add(int u, int v) { T[++edge_num] = (edge) {head[u], v}; head[u] = edge_num; } inline void Add(int &a, int b) { a += b; if (a >= Mod) a -= Mod; } void dfs(int x, int fa) { siz[x] = 1; for (int i = 1; i <= k; i++) f[x][0][i] = 1; for (int i = head[x]; i; i = T[i].nxt) { int son = T[i].to; if (son == fa) continue; dfs(son, x); memset(t, 0, sizeof(t)); for (int i = 0; i <= k * siz[x]; i++) for (int j = 0; j <= k; j++) if (f[x][i][j]) for (int p = 0; p <= k * siz[son]; p++) for (int q = 0; q <= k; q++) if (f[son][p][q]) Add(t[i + p + q][max(i + j + p, i + p + q) - (i + p + q)], 1ll * f[x][i][j] * f[son][p][q] % Mod); memcpy(f[x], t, sizeof(t)); siz[x] += siz[son]; } } int main() { scanf("%d%d", &n, &k); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); add(u, v), add(v, u); } dfs(1, 0); for (int i = 1; i <= k * n; i++) { int ans = 0; for (int d = 0; d <= min(i, k); d++) Add(ans, f[1][i - d][d]); printf("%d\n", ans); } return 0; } ```