一眼经典的树上背包
\(f[x][s][0/1]\)表示在x的子树中有s个连通块，选不选x的方案数
那么转移的话就是按照背包的转移即可
然后隐约记得这个是\(O(n^2)\)的
但是一直TLE，后面发现是有一个地方写法有问题，应该在计算完当前子树后再更新的size，这样可以保证复杂度。
实际跑起来会更快。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef long long ll;
const int N=5005;
const ll mo=998244353;
ll f[N][N][2],g[N][N][2];
int tot,head[N],to[N*2],nex[N*2],n,sz[N];
int x,y;
void add(int x,int y){
to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void ADD(ll &x,ll y){
x=(x+y)%mo;
}
void dfs(int x,int y){
sz[x]=1;
g[x][1][1]=1;
g[x][0][0]=1;
for (int i=head[x];i;i=nex[i]){
int v=to[i];
if (v==y) continue;
dfs(v,x);
fo(k,0,sz[x]) {
fo(s,0,sz[v]) {
ADD(f[x][k+s][1], g[x][k][1]*f[v][s][0]%mo + g[x][k+1][1]*f[v][s][1]%mo);
ADD(f[x][k+s][0], (f[v][s][0]+ f[v][s][1])%mo *g[x][k][0] %mo);
}
}
sz[x]+=sz[v];
fo(k,0,sz[x]) {
g[x][k][0]=f[x][k][0];
g[x][k][1]=f[x][k][1];
f[x][k][0]=f[x][k][1]=0;
}
}
fo(k,0,sz[x]) f[x][k][0]=g[x][k][0], f[x][k][1]=g[x][k][1];
while (!f[x][sz[x]][0] && !f[x][sz[x]][1] && sz[x]) sz[x]--;
}
int main(){
// freopen("data.in","r",stdin);
scanf("%d",&n);
fo(i,1,n-1){
scanf("%d %d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,0);
fo(i,1,n) printf("%lld\n",(f[1][i][0]+f[1][i][1])%mo);
return 0;
}