ARC087 F - Squirrel Migration

これ800点ってマジ？ムズすぎてハゲた

問題

n頂点の木があり、全ての頂点にリスがいる
長さnの順列pを決め、頂点iのリスを頂点p[i]に移動させる
各リスの移動距離の総和が最大になるようなpは何通りあるか

2 <= n <= 5000

解法

x-yを繋ぐ辺を通るリスの数の最大値は、xyそれぞれを根とする部分木をtx, tyとすると、
2 * min(|tx|, |ty|) である
サイズが小さい方の部分木のリスが全てもう片方の部分木に移動する場合にこうなる

○木の重心が2個ある場合
重心間の辺について↑の条件を満たせば他の全ての辺も条件を満たす
重心が2個ある場合、各重心を根とする部分木のサイズはどちらもn/2になるから、答えは{(n/2)!}^2

○重心が1個しかない場合
重心から伸びている辺全てについて↑の条件を満たせば他の全ての辺も条件を満たす
各部分木の全リスが「元々いた部分木上の頂点」以外のどこかに行くような順列pの個数を求めればいい
これは部分木ごとにサイズが違うから重心が2個の場合ほど単純には行かない
ここで余事象の「同じ部分木に留まるようなリスが1匹以上存在する」を考える
明らかにこっちの方が考えやすそうだからこっちを包除原理で求める

重心に隣接する各頂点を根とする部分木をT1, T2, ..., Tkとする
以下数式が複雑でタイプするのめんどいからクソ汚いメモをそのまま貼ります
途中で|T|とかΣ|Ti|って何回か書いてるけどこれは明らかにn-1(重心以外の全頂点の個数)
あと最後の行のdp[|T|][x]はdp[k][x]の間違い

実装(プログラムの流れ)

f[i]: iの階乗 は最初に求めておく

頂点0を仮の根とし、rec()で各頂点vを根とする部分木のサイズsz[v]を求めつつ重心を探す
直接の子c[i]全てについてsz[c[i]]がn/2以下 かつ n-sz[v]もn/2以下ならvは重心
(木の重心の詳細はググって)
gが1個目の重心でggが2個目の重心

2個目の重心ggが存在する場合は{(n/2)!}^2を出力して終了

次に重心gを木の根とし、rec2()で各頂点vを根とする部分木のサイズsz[v]を求める
gに隣接する頂点を根とする部分木のサイズをvector tにしまう (tのサイズがk)
あとは↑の通りにdpして包除原理

comb(n,k) = nCk は省略

#define int long long

int n, a, b, sz[5050], g = -1, gg = -1, f[5050], k, dp[5050][5050], res;
vector<int> e[5050], t;

int rec(int v, int p) {
	bool gp = 1;
	sz[v] = 1;
	each(i,e[v]) if (i!=p) {
		int tmp = rec(i,v);
		if (tmp>n/2) gp = 0;
		sz[v] += tmp;
	}
	if (gp && n-sz[v]<=n/2) {
		if (g==-1) g = v;
		else gg = v;
	}
	return sz[v];
}

int rec2(int v, int p) {
	each(i,e[v]) if (i!=p) sz[v] += rec(i,v);
	return sz[v];
}

signed main() {
	f[0] = 1;
	reps(i,1,5050) f[i] = f[i-1]*i %mod;
	cin >> n;
	rep(i,n-1) {
		cin >> a >> b;
		a--, b--;
		e[a].push_back(b), e[b].push_back(a);
	}
	rec(0,-1);
	if (gg!=-1) return cout << f[n/2]*f[n/2] %mod, 0;
	memset(sz, 0, sizeof(sz));
	rec2(g,-1);
	each(i,e[g]) t.push_back(sz[i]), k++;
	dp[0][0] = 1;
	rep(i,k) {
		int sum = 0;
		rep(j,i) sum += t[j];
		rep(x,sum+1) rep(y,t[i]+1)
			(dp[i+1][x+y] += dp[i][x] * comb(t[i],y) %mod * comb(t[i],y) %mod * f[y]) %= mod;
	}
	rep(i,n) (res += dp[k][i] * f[n-i] * (i%2 ? -1 : 1)) %= mod;
	(res += mod) %= mod;
	cout << res << endl;
}

冷静に見ると1つ1つはそこまで難しくない典型の組み合わせなんだよな
論理的思考+典型力で解ける問題ではあるんだろうな

https://beta.atcoder.jp/contests/arc087/tasks/arc087_d