Typical DP Contest N - 木

問題

n頂点からなる木が与えられる。
この木を、辺を一本ずつ書いていく。書いている途中の辺は全て連結であるようにしたい。

辺を書く順番は何通りあるかmod 10^9 + 7で求めよ。

制約条件

n≦1000

方針

木の根rを固定して考える。
dp[i]を、頂点i以下の部分木で、iとiの親の辺が既に書いてあるときの、
部分木の書き方の場合の数とする。

iとiの親の辺が既にあるので、
iからは子を順番に書いていくしかない。子がp, qのときは、
dp[i] = C(sz(p) + sz(q), sz(p)) * dp[p] * dp[q]という感じになる。
三つ以上のときも同様に辺の順番に自由度がある。

これで、dp[r]はrから辺を書き始めたときの総数になるので、
rを全ての頂点について動かして和を取ればよい。

ソースコード

pair<ll, int> rec(int c, int p){
	ll res = 1, sz = 0;
	
	rep(i, e[c].size()) if(e[c][i] != p){
		
		pi x = rec(e[c][i], c);
		res = res * x.first % mod;
		res = res * inv(fact[x.second]) % mod;
		sz += x.second;
	}
	res = res * fact[sz] % mod;
	
	return mp(res, sz + 1);
}
ll calc(int root){
	return rec(root, root).first;
}
 
int main(){
	fact[0] = 1;
	rep(i, 1000) fact[i+1] = fact[i] * (i+1ll) % mod;
	
	cin >> n;
	e.resize(n);
	
	rep(i, n - 1){
		int a, b;
		cin >> a >> b;
		a--; b--;
		e[a].pb(b);
		e[b].pb(a);
	}
	
	ll ans = 0;
	rep(i, n) ans += calc(i);
	cout << ans % mod * inv(2) % mod << endl;
	
	return 0;
}

残り、G, Sの解説書けばコンプリート。