题解：AT_abc287_f [ABC287F] Components

· · 题解

一个显然的树上背包。

设 dp_{u,k,0/1} 表示以 u 为根的子树中有 k 个连通块，且 u 是否在点集中的方案数。

枚举 u 当前子树的连通块个数 i，u 的子节点 v 的连通块个数 j，转移方程：

主要是代码的实现：

  1. 只有 u 的子树中至少有一个连通块时才能选 u 本身。
  2. 为了避免重算，需要将 dp_{u} 复制到 t 中，将 dp_u 清空，再使用 t 转移 dp_u。
  3. 记得取模。

代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 5050, MOD = 998244353;

int n, dp[N][N][2], t[N][2], sz[N];
vector<int> e[N];

void dfs(int now, int fa){
    sz[now] = 1; dp[now][1][1] = dp[now][0][0] = 1;
    for(int u : e[now]){
        if(u == fa) continue;
        dfs(u, now);
        for(int i = 0; i <= sz[now]; i ++){
            t[i][0] = dp[now][i][0];
            t[i][1] = dp[now][i][1];
            dp[now][i][0] = dp[now][i][1] = 0;
        }
        for(int i = 0; i <= sz[now]; i ++){
            for(int j = 0; j <= sz[u]; j ++){
                dp[now][i + j][0] = (dp[now][i + j][0] + (ll)t[i][0] * dp[u][j][0] % MOD) % MOD;
                if(j > 0) dp[now][i + j][0] = (dp[now][i + j][0] + (ll)t[i][0] * dp[u][j][1] % MOD) % MOD;
                if(i > 0) dp[now][i + j][1] = (dp[now][i + j][1] + (ll)t[i][1] * dp[u][j][0] % MOD) % MOD;
                if(i > 0 && j > 0) dp[now][i + j - 1][1] = (dp[now][i + j - 1][1] + (ll)t[i][1] * dp[u][j][1] % MOD) % MOD;
            }
        }
        sz[now] += sz[u];
    }
}

int main() {
    cin >> n;
    for(int i = 1, u, v; i < n; i ++){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    } 
    dfs(1, 0);
    for(int j = 1; j <= n; j ++)
        cout << (dp[1][j][0] + dp[1][j][1]) % MOD << endl;
    return 0;
}