ARC057 D - 全域木

問題文

http://arc057.contest.atcoder.jp/tasks/arc057_d

解法

メモ化再帰で解きます．
$rec(C) := $連結成分の状態が $C$ であるような状態から始めたときに，条件を満たすような辺の張り方の総数

$A[i]$ を小さい方から張って順に張っていくとき，$A[i]$に含まれない辺は，それまでにクラスカル法の要領で作られていた連結成分同士を結ばないように辺をはる必要があります．
逆に，$A[i]$ に含まれる辺は，連結成分同士を結ぶように辺を張ることになります．

今 $A[i]$ の辺を張ろうとした時，仮に連結成分の集合が $C = \{C_1, C_2, \ldots, C_k\}$ であったとしましょう．この時，重みが $A[i - 1] + 1$ から $A[i] - 1$ である辺は，$\displaystyle \sum_{i=1}^{k} \frac{|C_i|(|C_i| - 1)}{2} - (N - |C|)$ 本のまだ辺が張られていないところから適当に選ぶ必要があるので，これは単純に順列の総数を求めれば良いです．（$N - |C|$ はMSTにすでに使われている辺の数）
次に $A[i]$ を張るときは，連結成分から適当に2個選んでそれらを併合して，再帰的に解きます．例えば $C_i$ と $C_j$ を併合するときは，どの頂点同士を結ぶかで $|C_i| \times |C_j|$ 通りあります．
最後にすべての併合を試したものの総和に，$A[i - 1]$ から $A[i]$ までの辺の張り方をかけると答えになります．

$C$ の状態数は $N = 30$ の時高々5000程度（分割数という）なので，十分間に合います．

実装面では，番兵として $A[i]$ に 0 と $\frac{N(N - 1)}{2}$ を最初と最後に入れておくと楽かも？

ソースコード

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

using pii = pair<int, int>;
using ll = long long;

constexpr ll M = 1e9 + 7;

map<vector<int>, ll> memo;

ll rec(vector<int> C, vector<int> const& A) {
    sort(C.begin(), C.end());
    if(memo.count(C) == 1) {
        return memo[C];
    }

    int const N = A.size() - 1;

    ll t = 0; // 連結成分内で，使うと閉路が出来てしまう辺
    for(auto sz : C) {
        t += sz * (sz - 1) / 2;
    }
    int now = N - C.size(); // 次に加える辺
    t -= A[now];
    ll unuse = 1; // MSTで使わない辺の張り方
    for(int i = 0; i < A[now + 1] - A[now] - 1; ++i, --t) {
        unuse = unuse * t % M;
    }
    if(unuse == 0) { // どうしても A[i] 以外の辺を使うハメになる
        return memo[C] = 0;
    }

    // 連結成分同士の結び方
    if(C.size() == 1) {
        return memo[C] = unuse;
    } else {
        ll res = 0;
        int const m = C.size();
        for(int i = 0; i < m; ++i) {
            for(int j = i + 1; j < m; ++j) {
                vector<int> nC;
                nC.push_back(C[i] + C[j]);
                for(int k = 0; k < m; ++k) {
                    if(k != i && k != j) {
                        nC.push_back(C[k]);
                    }
                }
                res = (res + rec(nC, A) * C[i] * C[j]) % M;
            }
        }
        return memo[C] = (res * unuse) % M;
    }
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N + 1);
    for(int i = 1; i < N; ++i) {
        cin >> A[i];
    }
    A[N] = N * (N - 1) / 2 + 1; // 番兵
    vector<int> C(N, 1);
    cout << rec(C, A) << endl;
}