1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| #include <bits/stdc++.h> using namespace std; const int N = 1e2 + 5,P = 998244353; inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;} int fac[N],ifac[N],inv[N]; inline void init(int n) { fac[0] = 1; for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P; inv[1] = 1; for(int i = 2;i <= n;i++) inv[i] = 1ll * inv[P % i] * (P - P / i) % P; ifac[0] = 1; for(int i = 1;i <= n;i++) ifac[i] = 1ll * ifac[i - 1] * inv[i] % P; } inline int C(int n,int m) { if(n < 0 || m < 0 || n < m) return 0;return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;} inline int invC(int n,int m) { if(n < 0 || m < 0 || n < m) return 0;return 1ll * ifac[n] * fac[m] % P * fac[n - m] % P;} int dp[N][N][N],sze[N]; int n,K; vector<int> G[N];
void DP(int x,int fa) { static int tmp[N][N]; memset(tmp,0,sizeof tmp); memset(dp[x],0,sizeof dp[x]); dp[x][0][0] = 1;sze[x] = 0; int cnt = 0; for(auto y : G[x]) { if(y == fa) continue; DP(y,x);++cnt; for(int a = 0;a <= sze[x];a++) for(int b = 0;a + b <= sze[x];b++) { Plus(tmp[a][b + 1],dp[x][a][b]); for(int c = 0;c <= sze[y];c++) for(int d = 0;c + d <= sze[y];d++) Plus(tmp[a + c][b + d],1ll * dp[x][a][b] * dp[y][c][d] % P); } sze[x] += sze[y]; for(int a = 0;a <= sze[x];a++) for(int b = 0;a + b <= sze[x];b++) dp[x][a][b] = tmp[a][b],tmp[a][b] = 0; } ++sze[x]; for(int a = sze[x];a >= 1;a--) for(int b = 0;a + b <= sze[x];b++) dp[x][a][b] = dp[x][a - 1][b],dp[x][a - 1][b] = 0; } int Solve(int x) { int res = 0; DP(x,0); for(int a = K + 1;a <= n;a++) for(int b = 1;a + b <= n;b++) { Plus(res,1ll * dp[x][a][b] * invC(a + b,a) % P * inv[a] % P); } return res; } int main() { cin >> n >> K; for(int i = 1,a,b;i < n;i++) cin >> a >> b,G[a].push_back(b),G[b].push_back(a); init(n); int res = 1; for(int i = 1;i <= n;i++) Plus(res,Solve(i)); cout << res << endl; return 0; }
|