P6277 [USACO20OPEN] Circus P

Aria-Math / 2024-10-10 / 原文

做法来自浙江队长,因为其他的题解我一篇都看不懂。

考察一条极长的二度链 C,即左右端点度数不为 \(2\),中间的点度数都等于 \(2\),它把整张图分成了左右两部分 A 和 B(端点既属于 AB 也属于 C)。如果 \(|C| \ge n - k\),那么 A 和 B 都一定被占满了,C 上的点一定会阻挡 A 和 B 之间互换,所以可以分解成两个子问题。特殊的,钦定递归 A 时 C 上的奶牛都在靠近 B 的一边,递归 B 时都在靠近 A 的一边,这样每次递归时 \(n - k\) 不变。

\(r = |C| - n + k\),即 C 上的奶牛数。他们之间的顺序是固定了的,所以方案数为 \(\dbinom{k}{r}r!\),然后分解成 A 和 B 两个子问题后,分配到两边的方案数是 \(\dbinom{n-r}{A}\)。当分解到联通块内没有 \(|C| \ge n - k\) 的链时,联通块内两两可交换,方案数是 \(1\)

动态的过程不好维护,考虑对每个部分在递归到最底层时统计。本质上是多重组合数,每个联通块贡献 \(\dfrac{1}{cow_i!}\),每条断掉的边贡献的系数和阶乘抵消所以不用考虑,最后乘上 \(k!\) 即可。

计算每个联通块最后的奶牛数:断开每条极长链时会新增 \(n - k - 1\) 个空白点,但是要去掉最后一次断开,则有 \(cow_i = siz_i + out_i \cdot (n-k-1)-(n-k)\)。从大到小枚举 \(k\),则相当于不断加边。维护 \(siz_i\)\(out_i\) 即可。

// They say that life is always easier
// After you let yourself come undone
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
struct Node {
	int u, v, w;
} E[N];
int n, cnt, deg[N], dsu[N], siz[N], out[N];
ll fac[N], ifac[N], ans[N];
set<int> st;
vector<int> G[N];
void Dfs(int u, int fat, int lst, int sum) {
	if(deg[u] != 2) {
		if(lst) E[++cnt] = {lst, u, sum};
		st.insert(lst = u), sum = 1;
	}
	for(int v : G[u]) if(v != fat)
		Dfs(v, u, lst, sum + 1);
}
ll Pow(ll a, int p = MOD - 2) {
	ll ans = 1;
	for(; p; p >>= 1, a = a * a % MOD)
		if(p & 1) ans = ans * a % MOD;
	return ans;
}
ll C(int n, int m) {
	if(n < 0 || m < 0 || n < m) return 0;
	return fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
int Find(int u) {
	if(u == dsu[u]) return u;
	return dsu[u] = Find(dsu[u]);
}
void Solve() {
	cin >> n;
	for(int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
		++deg[u], ++deg[v];
	}
	for(int i = 1; i <= n; ++i) if(deg[i] != 2) {
		Dfs(i, 0, 0, 1); break;
	}
	for(int i = 1; i <= n; ++i)
		dsu[i] = i, siz[i] = 1, out[i] = deg[i];
	sort(E + 1, E + cnt + 1, [](Node a, Node b) {
		return a.w < b.w;
	});
	fac[0] = 1;
	for(int i = 1; i <= n; ++i)
		fac[i] = fac[i - 1] * i % MOD;
	ifac[n] = Pow(fac[n]);
	for(int i = n - 1; i >= 0; --i)
		ifac[i] = ifac[i + 1] * (i + 1) % MOD;
	ans[n] = fac[n], ans[n - 1] = fac[n - 1];
	int now = 1;
	for(int k = n - 2; k >= 1; --k) {
		while(now <= cnt && E[now].w < n - k) {
			int x = Find(E[now].u), y = Find(E[now].v);
			dsu[x] = y, siz[y] += siz[x] + E[now].w - 2;
			out[y] += out[x] - 2, ++now, st.erase(x);
		}
		ans[k] = fac[k]; int r = k;
		for(int i : st) {
			int s = siz[i] + (n - k - 1) * out[i] - (n - k);
			ans[k] = ans[k] * ifac[s] % MOD, r -= s;
		}
	}
	for(int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
}
int main() {
#ifndef ONLINE_JUDGE
	freopen("data.in", "r", stdin);
	freopen("code.out", "w", stdout);
#endif
	cin.tie(0)->sync_with_stdio(0);
	int t = 1; //cin >> t;
	while(t--) Solve();
	return 0;
}