SRM 559 div1 med HatRack

問題

TopCoder Statistics - Problem Statement

頂点の接続関係が与えられる。
以下の性質を持つような木の場合の数を求めよ。

• 葉を除くすべての頂点は, 子を 1 つか 2 つ持つ
• 木の根からの距離を rank とすると, rank = k の場所には 2^k 個(ただし rank が最大のところではこの制限はない)
• rank が最大のところの頂点は, なるべく左側に詰められる(詳しいことは問題文読んで)

解法

dp します。

dp[rank][col][v][p] = (高さ rank の col 番目の頂点が v で, その親が p であるような場合の数) とします。すると,

• v が葉の時は v の次数が 1 なら 答えは 1, そうでないなら 0
• 子供が 1 つしかない場合は, 次数が 2 でないと答えは 0
  • 次数が 2 の時は, p 以外の接続頂点を選んで dp[rank+1][2*col][ch][v] を求める
• 子供が 2 つの場合は, 次数が 3 でないと答えは 0
  • p 以外の接続頂点を選んで, ch1 を左, ch2 を右にした場合と ch1 を右, ch2 を左にした場合の和が答え

でいけます。

根を全探索して, 和を求めましょう。

ll dp[10][32][55][55];
int Rank = 0;
// 葉の数
int bottomNum, upperNum = 0;
vector<int> G[55];

// rank の col 番目に num があるような場合の数
ll dfs(int rank, int col, int v, int p) {
    //cout << rank << " " << col << " " << v << " " << p << endl;
    ll& ret = dp[rank][col][v][p];
    if (ret >= 0) return ret;
    ret = 0;
    int colNum = 1<<rank;
    if (rank == Rank-1 || (rank == Rank-2 && col >= colNum-upperNum)) {
        return ret = (G[v].size() == 1);
    }
    // ひとつだけ
    if (rank == Rank-2 && bottomNum%2 == 1 && col == bottomNum/2) {
        if (G[v].size() != 2) return ret = 0;
        for (int ch : G[v]) {
            if (ch == p) continue;
            ret += dfs(rank+1, 2*col, ch, v);
        }
        return ret;
    }
    vi children;
    for (int ch : G[v]) if (ch != p)
        children.push_back(ch);
    if (children.size() != 2) return ret = 0;
    ret += dfs(rank+1, 2*col, children[0], v) * dfs(rank+1, 2*col+1, children[1], v);
    ret += dfs(rank+1, 2*col, children[1], v) * dfs(rank+1, 2*col+1, children[0], v);
    return ret;
}

class HatRack {
public:
    long long countWays(vector <int> knob1, vector <int> knob2) {
        for (int i = 0; i < 55; i++)
            G[i].clear();
        int n = knob1.size() + 1;
        if (n == 2) return 2;
        Rank = 0;
        while ((1<<Rank)-1 < n) Rank++;
        cout << Rank << endl;
        bottomNum = n - (1<<(Rank-1)) + 1;
        upperNum = (1<<(Rank-2)) - bottomNum/2 - bottomNum%2;
        cout << bottomNum << " " << upperNum << endl;
        for (int i = 0; i < n-1; i++) {
            G[knob1[i]].push_back(knob2[i]);
            G[knob2[i]].push_back(knob1[i]);
        }
        memset(dp, -1, sizeof(dp));
        ll ret = 0;
        for (int i = 1; i <= n; i++) {
            ret += dfs(0, 0, i, 0);
        }
        return ret;
    }
};