[ARC087F] Squirrel Migration

模拟赛题，不知道为什么放在最后一题，感觉评分过高了。

首先是经典问题，最大值是 \(\sum \min(siz, n-siz)\)，证明考虑每条边上界。

考虑证明的构造，对于重心的每个儿子拉出子树，求出子树大小即可转为序列上问题：每个点不跟内部匹配即可满足最大，容易证明充要。

朴素 dp 发现怎么也避不开两维状态，非常没有前途。

考虑二项式反演，钦定 \(x\) 个点与自己匹配，剩下的方案是好算的，于是 \(f_{i,j}\) 表示考虑前 \(i\) 个子树，其中钦定的有 \(j\) 个的方案，转移枚举这个子树钦定几个，方案数是 \(\binom{siz}{k}^2*fac_k\)，统计答案时对于剩下的 \(n-j\) 个点可以随便匹配。

复杂度是 \(O(n^2)\)，证明考虑类似树形背包，任意两个点只会被算一次。

const int N = 5005;
int n;
vector <int> e[N];
int A, B, siz[N], rt, rt_siz;
void find_rt(int u, int fa) {
	siz[u] = 1;
	int mx = 0;
	for (auto v : e[u]) if (v != fa) {
		find_rt(v, u);
		siz[u] += siz[v];
		ckmax(mx, siz[v]);
	}
	ckmax(mx, n - siz[u]);
	if (!rt || mx < rt_siz) rt = u, rt_siz = mx;
}
void dfs(int u, int fa) {
	siz[u] = 1;
	for (auto v : e[u]) if (v != fa) dfs(v, u), siz[u] += siz[v];
}
int w[N], tot;
int f[N], g[N], fac[N], inv[N];
void init(int lim) {
	fac[0] = 1;
	for (int i = 1; i <= lim; i++) fac[i] = Cmul(fac[i - 1], i);
	inv[lim] = ksm(fac[lim], mod - 2);
	for (int i = lim; i >= 1; i--) inv[i - 1] = Cmul(inv[i], i);
}
int binom(int n, int m) {
	if (n < m || m < 0) return 0;
	return Cmul(fac[n], inv[m], inv[n - m]);
}

void main01() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	find_rt(1, 0);
	for (auto v : e[rt]) dfs(v, rt), w[++tot] = siz[v];
	init(n);
	f[0] = 1;
	for (int o = 1, sum = 0, siz; o <= tot; o++) {
		siz = w[o];
		for (int j = 0; j <= sum; j++) if (f[j]) {
			for (int k = 0; k <= siz; k++) {
				Madd(g[j + k], Cmul(f[j], binom(siz, k), binom(siz, k), fac[k]));
			}
		}
		sum += siz;
		for (int j = 0; j <= sum; j++) f[j] = g[j], g[j] = 0;
	}
	for (int i = 0; i <= n; i++) Mmul(f[i], fac[n - i]);
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		if (i & 1) Mdel(ans, f[i]);
		else Madd(ans, f[i]);
	}
	cout << ans << '\n';
}