自动搬运

查看原文

来自洛谷，原作者为

	Un1quAIoid **

搬运于2025-08-24 22:38:19，当前版本为作者最后更新于2022-05-18 09:46:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

传送门：P8352 [SDOI/SXOI2022] 小 N 的独立集

---

题意

给定 $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$）：

//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;
}