Submission #45747541

---

Source Code Expand

// LUOGU_RID: 125305561
#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> inline void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> inline void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
const int N = 110, MOD = 998244353;
int n, k, f[N][N][N], sz[N], g[N][N], ans;
vector <int> v[N];
inline void add(int &x, ll y) { x = (x + y) % MOD; }
int fac[N], ifac[N], inv[N];
inline void binom(int x) {
	fac[0] = ifac[0] = inv[1] = 1;
	F(i, 2, x) inv[i] = (ll) (MOD - MOD / i) * inv[MOD % i] % MOD;
	F(i, 1, x) fac[i] = (ll) fac[i - 1] * i % MOD, ifac[i] = (ll) ifac[i - 1] * inv[i] % MOD;
}
inline int C(int x, int y) { return x < y || y < 0 ? 0 : (ll) fac[x] * ifac[y] % MOD * ifac[x - y] % MOD; }
void dfs(int x, int fa) {
	f[x][sz[x] = 1][0] = 1;
	for (int i: v[x])
		if (i != fa) {
			dfs(i, x);
			ms(g, 0);
			F(aa, 1, sz[x])
				F(ab, 0, sz[x] - aa)
					if (f[x][aa][ab]) {
						F(ba, 1, sz[i])
							F(bb, 0, sz[i] - ba)
								add(g[aa + ba][ab + bb], (ll) f[x][aa][ab] * f[i][ba][bb]);
						add(g[aa][ab + 1], f[x][aa][ab]);
					}
			sz[x] += sz[i];
			F(a, 1, sz[x])
				F(b, 0, sz[x] - a)
					f[x][a][b] = g[a][b];
		}
	// F(a, 1, sz[x])
	// 	F(b, 0, sz[x] - a)
	// 		if (f[x][a][b]) cout << x << " " << a << " " << b << " " << f[x][a][b] << endl;
	F(a, k + 1, sz[x])
		F(b, 0, sz[x] - a) {
			int bb = b + !!fa;
			// cout << x << "~ " << a << " " << b << " " << f[x][a][b] << endl;
			// cout << " -> " << bb << " " << C(a + bb, a) << " " << a + bb << endl;
			add(ans, (ll) fac[a] * fac[bb] % MOD * ifac[a + bb] % MOD * f[x][a][b]);
			// cout << fac[a] * fac[bb] << " " << fac[a + bb] << endl;
			// cout << ans << endl;
		}
}
signed main() {
	read(n), read(k);
	binom(n);
	F(i, 2, n) {
		int x, y; read(x), read(y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1, 0);
	cout << ans;
	return 0;
}

Submission Info

Judge Result