Typical DP Contest N - 木

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_tree

解法

まず，一番最初に書き始める辺を定めることを考える．
そして，定めた辺を縮約したグラフ上で，以下の問題を解けば良い．
「縮約してできた頂点を根として，そこから辺を生やしていく方法は何通りあるか？」
これは DFS で再帰的に解ける．
例えば，縮約した頂点を v として，v から辺が2本生えている状況を考える．
大きく2つの部分木 t1 と t2 に別れることになるが，部分木のサイズと，部分木の辺の生やし方の総数がそれぞれ (s1, x1), (s2, x2) であるとしよう．
こうすると，グラフ全体では \(_{s_1+s_2}C_{s1} \times x_1 \times _{s_2}C_{s_2} \times x_2\) の辺の生やし方があることになる．
これを以下で説明する．
s1 + s2 回の操作列で，どのタイミングで t1 の頂点を追加するかの場合の数は，s1 + s2 から s1 個を選ぶ \(_{s_1 + s_2}C_{s1}\)通りである．場所が決まったら，あとは具体的に t1 の頂点をどう s1 箇所に配置するかだが，これはすでに x1 通りであるとわかっている．
t2 の頂点に関しても同様に，残った場所に配置して，具体的にどういう順番かは求まっている(y)ので，結果として先程の式が得られる．

これは，部分木がたくさんあっても同様にできる．部分木の部分木についても，再帰的に同様のことをやっていくだけである．

最初の辺を定めるのと，定めたあとのDFSで，計算量は O(N^2) となる．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;

constexpr ll M = 1e9 + 7;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

ll inv(ll a, ll p) {
    return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}

ll fact(int n, bool inv_) {
    static vector<ll> v1 = {1}, v2 = {1};
    if(n >= (int)v1.size()) {
        int const from = v1.size(), to = n + 1024;
        v1.reserve(to);
        v2.reserve(to);
        for(int i = from; i < to; ++i) {
            v1.push_back(v1.back() * i % M);
            v2.push_back(v2.back() * inv(i, M) % M);
        }
    }
    return inv_ ? v2[n] : v1[n];
}

ll comb(int n, int r) {
    if(r < 0 || r > n) {
        return 1;
    }
    ll res = fact(n, false) * fact(r, true) % M;
    res = res * fact(n - r, true) % M;
    return res;
}

using graph = vector<vector<int>>;

pll dfs(ll v, int prev, graph const& g) {
    auto res = make_pair(1, 1);
    vector<pll> child;
    ll sum = 0;
    for(auto to : g[v]) {
        if(to == prev) {
            continue;
        }
        auto t = dfs(to, v, g);
        sum += t.second;
        child.push_back(move(t));
    }
    res.second += sum;
    for(auto& p : child) {
        res.first = res.first * comb(sum, p.second) % M;
        res.first = res.first * p.first % M;
        sum -= p.second;
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<pii> es(N - 1);
    for(int i = 0; i < N - 1; ++i) {
        cin >> es[i].first >> es[i].second;
        es[i].first--;
        es[i].second--;
    }

    ll res = 0;
    for(int i = 0; i < N - 1; ++i) {
        graph g(N);
        int root = es[i].first;
        for(int j = 0; j < N - 1; ++j) {
            if(i == j) {
                continue;
            }
            int u = es[j].first, v = es[j].second;
            if(u == root || u == es[i].second) {
                g[root].push_back(v);
                g[v].push_back(root);
            } else if(v == root || v == es[i].second) {
                g[root].push_back(u);
                g[u].push_back(root);
            } else {
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
        res = (res + dfs(root, -1, g).first) % M;
    }

    cout << res << endl;
}

感想

全然わからなくて結局教えてもらった問題です．
組み合わせの式は，以下のように説明してもらってやっと気が付きました．
「長さ n の文字列 S と 長さ m の文字列 T があり，S と T の両方に現れる文字はありません．S と T を部分列として含む長さ n + m 文字列の文字列は何通りあるでしょう？」
これは $_{n+m}C_n$ ですが，考え方は全く同じです．
結局知ってる問題に落とせたわけですが，形が変わっただけで見抜けなくなってしまうのは反省しなければなりません…．