Submission #38402744

---

Source Code Expand

#include<bits/stdc++.h>
#define N 5009
using namespace std;
typedef long long ll;
const int mod=998244353;
int n;
int head[N],tot,dp[N][N][2],siz[N],g[N][2];
inline ll rd(){
	ll x=0;char c=getchar();bool f=0;
	while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?-x:x;
}
struct edge{
	int n,to;
}e[N<<1];
inline void add(int u,int v){
	e[++tot].n=head[u];
	e[tot].to=v;
	head[u]=tot;
}
void MOD(int &x){
	x=x>=mod?x-mod:x;
} 
void dfs(int u,int fa){
	siz[u]=1;
	dp[u][1][1]=1;
	dp[u][0][0]=1;
	for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){
		int v=e[i].to;
		dfs(v,u);
		for(int j=0;j<=siz[u];++j)
		    for(int k=0;k<=siz[v];++k){
		    	MOD(g[j+k][1]+=1ll*dp[u][j][1]*dp[v][k][0]%mod);
		    	MOD(g[j+k][0]+=1ll*dp[u][j][0]*dp[v][k][0]%mod);
		    	MOD(g[j+k][0]+=1ll*dp[u][j][0]*dp[v][k][1]%mod);
		    	if(j&&k)MOD(g[j+k-1][1]+=1ll*dp[u][j][1]*dp[v][k][1]%mod);
			}
		siz[u]+=siz[v];
		for(int j=0;j<=siz[u];++j){
			dp[u][j][0]=g[j][0];
			dp[u][j][1]=g[j][1];
			g[j][0]=g[j][1]=0;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	int u,v;
	for(int i=1;i<n;++i){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=n;++i){
		cout<<(dp[1][i][0]+dp[1][i][1])%mod<<'\n';
	}
}

Submission Info

Judge Result