Typical DP Contest N - 木
解法
解いたときのメモ。
木dp で解くことを考えます。そうすると dp[v] = (v の部分木での場合の数), のようにするのが自然です。これの遷移を考えると, 上の写真のように,
子 v1 の部分木について辺を張る作業をするもの, 子 v2 の部分木について辺を張る作業をするもの, ... というのを好きな順番でやるものと考えることができます。この順番に関しての場合の数は, 「種類1 が s1 個, 種類2 が s2 個, ... とあるときのボールの並べ方」に等しく, 上の写真のびっくりマークがたくさんついてる式になります。
これをすべての頂点を root にしてやれば良いですが, a -> b と張るのと b -> a と張るのは同じことなので, 最後に /2 しましょう(いまいち /2 する理由がはっきりしないけどたぶんこういうことだよね)。
/2 しないといけないと思ったのは 1 - 2 という木に対して答えが 1 になるし 3 - 1 - 2 という木に対しては答えが 2 になるはずだと思ったからです。
ll mod_pow(ll x, ll p, ll MOD) { ll a = 1; while (p) { if (p%2) a = a*x%MOD; x = x*x%MOD; p/=2; } return a; } // mod_inverse ll mod_inverse(ll a, ll m) { return mod_pow(a, m-2, m); } const int MAXN = 1111; const int MOD = 1e9+7; vector<int> G[MAXN]; ll fact[MAXN], rfact[MAXN]; pair<ll, int> dfs(int v, int p) { pair<ll, int> ret; ret.first = 1; int sum = 0; for (int ch : G[v]) { if (ch == p) continue; auto p = dfs(ch, v); (ret.first *= p.first*mod_inverse(fact[p.second], MOD)%MOD) %= MOD; sum += p.second; } (ret.first *= fact[sum]) %= MOD; ret.second = sum+1; return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); fact[0] = rfact[0] = 1; for (int i = 1; i < MAXN; i++) { fact[i] = (fact[i-1]*i)%MOD; rfact[i] = mod_inverse(fact[i], MOD); } int N; cin >> N; for (int i = 0; i < N-1; i++) { int a, b; cin >> a >> b; a--; b--; G[a].push_back(b); G[b].push_back(a); } ll ans = 0; for (int i = 0; i < N; i++) { (ans += dfs(i, -1).first) %= MOD; } (ans *= mod_inverse(2, MOD)) %= MOD; cout << ans << endl; return 0; }