ABC287F Components题解

· · 题解

赛后十分钟做完此题，酸爽。

比较基础的树上背包DP。按照树上DP的套路，状态定义里面一定有 u 表示目前递归到以 u 为根的子树。另外因为要考虑连通块，自己这个点选不选会影响连通块的个数，用第二个维度表示 u 选不选。选多少个点显然也会影响决策，再加一维。这样状态定义就好了：

用 dp[u][0][i] 表示以 u 为根的子树，u 自己不选，整棵树里面总共选 i 个连通块的方案数有多少。用 dp[u][1][i] 表示以 u 为根的子树，u 自己选，整棵树里面总共选 i 个连通块的方案数有多少。

显然只考虑根自己的时候，有：dp[u][0][0] = 1 和 dp[u][1][1] = 1。

接下来考虑一个孩子一个孩子加进来，当前加进来的孩子是 v ，先递归调用 v 把它的所有dp值求好。然后考虑父子之间转移，当 u 以及 v 之前的孩子们中选 i 个连通块，v 中选 j 个连通块，如果 u 不选，那么总的连通块个数就是 i+j，因为它们相互之间被 u 分开，肯定不连通。此时计算连通块的个数可以直接乘法原理，转移代码：

dp[u][0][i + j] = (dp[u][0][i + j] + dp[u][0][i] * (dp[v][0][j] + dp[v][1][j]) % MOD) % MOD;

如果 u 选，v 不选，也是同理。唯一不同的是，如果 u 和 v 都选，总的连通块个数会少 1 个，因为 u 和 v 所在的两个连通块连一起了。代码时间复杂度 O(n^2)。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;
const ll MAXN = 5005;
const ll MOD = 998244353;
//dp[u][0][i]表示以u为根的子树，根不要，总共保留i个连通块的方案数。第二维1表示要根。
ll n, dp[MAXN][2][MAXN];
vector<int> adj[MAXN];

int dfs(int u, int f) {
    int tc = 1;//子树中点的数量
    dp[u][0][0] = 1;//初始化根的答案
    dp[u][1][1] = 1;
    for (int v: adj[u]) {
        if (v != f) {
            int ch = dfs(v, u);//递归调用孩子，保存孩子中点的数量
            //先计算u不要的情况
            for (int i = tc; i >= 0; --i) {
                for (int j = ch; j >= 1; --j) {
                    //注意这里j不取0，0的时候有一种方案，和原来的dp[u][0][i]乘完放回去，相当于dp[u][0][i]的值不动
                    //u不要，v要不要都行
                    dp[u][0][i + j] = (dp[u][0][i + j] + dp[u][0][i] * (dp[v][0][j] + dp[v][1][j]) % MOD) % MOD;
                }
            }
            //计算u要的情况
            for (int i = tc; i >= 1; --i) {
                for (int j = ch; j >= 1; --j) {
                    //注意这两句话顺序不能反，j等于1的时候，i + j - 1等于i，会改掉之前的值
                    dp[u][1][i + j] = (dp[u][1][i + j] + dp[u][1][i] * dp[v][0][j] % MOD) % MOD;
                    dp[u][1][i + j - 1] = (dp[u][1][i + j - 1] + dp[u][1][i] * dp[v][1][j] % MOD) % MOD;
                }
            }
            tc += ch;
        }
    }
    return tc;
}

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