1 条题解
-
0
#include<bits/stdc++.h> using namespace std; #define int long long const int N=5010,P=998244353; int dp[N][N][2],dp1[N][2],siz[N],n;vector<int>G[N]; void dfs(int x,int f) { dp[x][0][0]=dp[x][1][1]=1;siz[x]=1; for(int y:G[x])if(y!=f) { dfs(y,x); for(int i=0;i<=siz[x];i++)for(int j=0;j<=siz[y];j++)if(i+j-1<=n) { dp1[i+j][0]=(dp1[i+j][0]+dp[x][i][0]*dp[y][j][0])%P; dp1[i+j][0]=(dp1[i+j][0]+dp[x][i][0]*dp[y][j][1])%P; dp1[i+j][1]=(dp1[i+j][1]+dp[x][i][1]*dp[y][j][0])%P; if(i+j-1>=0)dp1[i+j-1][1]=(dp1[i+j-1][1]+dp[x][i][1]*dp[y][j][1])%P; } for(int i=0;i<=n;i++) dp[x][i][0]=dp1[i][0],dp[x][i][1]=dp1[i][1], dp1[i][0]=dp1[i][1]=0; siz[x]+=siz[y]; } } signed main() { cin>>n; for(int i=1;i<n;i++) { int x,y;cin>>x>>y; G[x].push_back(y); G[y].push_back(x); } dfs(1,0); for(int i=1;i<=n;i++)cout<<(dp[1][i][0]+dp[1][i][1])%P<<'\n'; return 0; }
- 1
信息
- ID
- 7780
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 10
- 标签
- 递交数
- 6
- 已通过
- 2
- 上传者