総神童数 [yukicoder No.827] - はまやんはまやんはまやん

解説

全探索対象を変えて数え上げるテクを使おう。
問題では順列をN!通り考えて、順列で神童数をそれぞれ数えて総和を取っている。
これを頂点をN通り考えて、その頂点が神童となる順列の組み合わせの総和を取ろう。
　
ある頂点が神童となる順列は、根からの深さdptを使って計算できる。
深さは根を1としておこう。
すると、組み合わせはC(N, dpt) * (dpt-1)! * (N - dpt)!となる。
C(N, dpt) * (dpt-1)!はNからdpt個選んで並べたときに最後の要素が最も大きくなる組み合わせ
ある頂点の要素が最も大きくなればいいので、この組み合わせを計算する。
(N - dpt)!は神童であるかどうかと関係が無い要素の組み合わせになる。
　
頂点Nをdfsで深さを測りながら全探索して、総和を取ると答え。

int N;
vector<int> E[201010];
Comb<mint, 401010> com;
//---------------------------------------------------------------------------------------------------
mint ans = 0;
void dfs(int cu, int pa = -1, int dpt = 1) {
	ans += com.aCb(N, dpt) * com.fac[dpt - 1] * com.fac[N - dpt];
	fore(to, E[cu]) if (to != pa) dfs(to, cu, dpt + 1);
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b;
		E[a].push_back(b);
		E[b].push_back(a);
	}

	dfs(1);
	cout << ans << endl;
}