P8352 SDOI2022 D2T1 小 N 的独立集 题解

· · 题解

传送门：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;
}