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