Typical DP Contest N - 木

問題

tdpc.contest.atcoder.jp

解法

解いたときのメモ。

木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;
}