ABC287F树形DP顺推

一棵树种保留1、2、3、……、n个连通块的方案数分别是多少？
显然树形DP，只是需要注意枚举的顺序、细节问题。
1、由背包枚举顺序可知，应从大到小枚举容量，保证用到的都是上次的。
2、子树b不需要枚举0个连通块，0个连通块就是自己本身的方案。
3、顺推不需要管太多细节，且枚举范围会小一些；倒退因为a和b都选，会少一个连通块，出现一些不好维护的顺序问题。

#include <stdio.h>
const int N=5005, mo=998244353;
int n, m, i, j, k, a, b, h[N], s[N];
long long f[N][N], g[N][N];
struct AB{
    int a, b, n;
} d[N*2];
void cun(int a, int b){
    d[++k].a = a, d[k].b = b;
    d[k].n = h[a], h[a] = k;
}
void dfs(int a, int p){
    int b, i, j, k;
    f[a][1] = g[a][0] = s[a] = 1;
    for(i=h[a]; i; i=d[i].n){
        b = d[i].b;
        if(b == p) continue;
        dfs(b, a);
        for(j=s[a]; j>=0; j--){
            for(k=s[b]; k; k--){
                f[a][j+k] += f[a][j] * g[b][k];
                f[a][j+k-1] += f[a][j] * f[b][k];
                f[a][j+k] %= mo, f[a][j+k-1] %= mo;
                g[a][j+k] += g[a][j] * f[b][k];
                g[a][j+k] += g[a][j] * g[b][k];
                g[a][j+k] %= mo;
            }//凑出j+k个连通块的方案数可以累加
        }//当前子树选择j个连通块，儿子选择k个连通块
        s[a] += s[b];//子树大小
    }
}//f[i][j]子树i有j个连通块，f是选i，g是不选i
int main(){
    scanf("%d", &n);
    for(i=1; i<n; i++){
        scanf("%d%d", &a, &b);
        cun(a, b);
        cun(b, a);
    }
    dfs(1, 0);
    for(i=1; i<=n; i++){
        printf("%lld\n", (f[1][i]+g[1][i])%mo);
    }
    return 0;
}