백준8916 이진 검색 트리

작성일 | In

문제 링크

  • http://icpc.me/8916

문제 출처

  • 2010 대전 리저널 E번

사용 알고리즘

  • DP

시간복잡도

  • $O(N + \log P)$

풀이

이진 트리를 위상 정렬하는 경우의 수를 구하는 문제입니다.

현재 정점 $v$의 자식 정점 $c_1, c_2$를 루트를 하는 서브트리를 위상 정렬하는 경우의 수를 각각 $f_1, f_2$, 서브트리의 크기를 각각 $s_1, s_2$라고 합시다. 첫번째 서브트리의 정점에 모두 1이라는 라벨을 붙이고, 두번째 서브트리의 정점에 모두 2라는 라벨을 붙이면, (중복이 있는 순열의 개수) * $f_1$ * $f_2$를 구하면 됩니다.

그러므로 $v$를 루트로 하는 서브트리를 위상 정렬하는 경우의 수는 $\frac{(s_1+s_2)!}{s_1!s_2!}f_1f_2$이고, 트리 DP를 이용해 문제를 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 9'999'991;
ll Pow(ll a, ll b){
    ll res = 1;
    for(; b; b >>= 1, a = a * a % MOD) if(b & 1) res = res * a % MOD;
    return res;
}

int N, A[22], C[22][2], S[22];
ll Fac[22], Inv[22];

void Insert(int x, int v){
    int &c = C[x][x < v];
    if(!c) c = v;
    else Insert(c, v);
}

ll DFS(int v){
    S[v] = 1;
    vector<ll> sz, dp;
    for(auto i : C[v]) if(i) dp.push_back(DFS(i)), sz.push_back(S[i]), S[v] += S[i];
    return Fac[accumulate(sz.begin(), sz.end(), 0)]
           * accumulate(sz.begin(), sz.end(), 1LL, [](ll a, ll b){ return a * Inv[b] % MOD; }) % MOD
           * accumulate(dp.begin(), dp.end(), 1LL, [](ll a, ll b){ return a * b % MOD; }) % MOD;
}

void Solve(){
    memset(C, 0, sizeof C);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=2; i<=N; i++) Insert(A[1], A[i]);
    cout << DFS(A[1]) << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    Fac[0] = 1; for(int i=1; i<22; i++) Fac[i] = Fac[i-1] * i % MOD;
    for(int i=0; i<22; i++) Inv[i] = Pow(Fac[i], MOD - 2);
    int T; cin >> T;
    while(T--) Solve();
}