pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CS Academy: Connected Tree Subgraphs

問題ページ

解法

$O(n^2)$ 解法は TDPC のという問題と同じ。

dp[v]:=vの部分木の番号の振り方を計算する。子が a,b,c,d だったとき、a,b,c,dのどれを進めるかで (A+B+C+D)!/A!B!C!D! 通りあって、それに番号の振り方を考慮すれば

$$ dp[v]=\frac{(A+B+C+D)!}{A!B!C!D!} dp[a]dp[b]dp[c]dp[d] $$

となる。

全ての頂点を根として dfs を回せば $O(n^2)$ になるが、それだと間に合わない。

こういうときは、まず 0 を根として普通に DP をする。

次にもう一回 DFS を掛けて、根を変えたときの DP の値を計算する。

再計算するためには親方向の DP の値を求める必要がある。祖先以外の頂点の DP の値は変わらないので再利用でき、 $O(n)$ で計算できる。

f:id:pekempey:20160825200332p:plain

O(n^2) でも自分には難しかった。

全方位木DPに関する考察

通常のDPをrooted-tree DP、全方位木DPを free-tree DPと便宜上呼ぶことにする。rooted-tree DPが可能ならばfree-tree DPが可能であるというのは経験的に正しそうである。rooted-tree DP を機械的に free-tree DP に変換したい。

基本的に木DPは以下の2操作によって実現できそうである。

  • add: 子要素のDP値を集計していく
  • bundle: addで集計した値を加工する

以下のように書ける rooted-tree DP を free-tree DP 化する関数を作成した。

function<void(int, int)> dfs = [&](int u, int p) {
    for (int v : g[u]) {
        if (v != p) {
            dfs(v, u);
            dp[u] = add(dp[u], dp[v]);
        }
    }
    dp[u] = bundle(dp[u]);
};

このように表現できるDPの例を示す。

木の高さ

// fooという構造体を定義しているが、intのままでも構わない。ただし単位元が-1であるため注意。
struct foo {
    int height;
    foo(int height = -1) : height(height) {}
};
auto add = [&](const foo &a, const foo &b) {
    return foo(max(a.height, b.height));
};
auto bundle = [&](const foo &a) {
    return foo(a.height + 1);
};

部分木のサイズ

// free-tree DP化しても結果は常にnになるため必要になる場面は存在しない。
auto add = [&](int a, int b) {
    return a + b;
};
auto bundle = [&](int a) {
    return a + 1;
};

この問題

struct foo {
    modint way = 1; // way=dp/fact[cnt]
    int cnt = 0;
};
auto add = [&](const foo &a, const foo &b) {
    foo ret;
    ret.way = a.way * b.way;
    ret.cnt = a.cnt + b.cnt;
    return ret;
};
auto bundle = [&](const foo &a) {
    foo ret;
    ret.way = a.way * fact[a.cnt] * ifact[a.cnt + 1];
    ret.cnt = a.cnt + 1;
    return ret;
};

codeforces 790B - Bear and Tree Jumps

struct foo {
    array<long long, 5> dist;
    array<int, 5> cnt;
    foo() : dist(), cnt() {}
};
auto add = [&](const foo &a, const foo &b) {
    foo ret;
    for (int i = 0; i < K; i++) {
        ret.dist[i] = a.dist[i] + b.dist[i];
        ret.cnt[i] = a.cnt[i] + b.cnt[i];
    }
    return ret;
};
auto bundle = [&](const foo &a) {
    foo ret;
    for (int i = 0; i < K; i++) {
        ret.dist[(i + 1) % K] = a.dist[i] + a.cnt[i];
        ret.cnt[(i + 1) % K] = a.cnt[i];
    }
    ret.cnt[0]++;
    return ret;
};

無引数のコンストラクタは単位元を返すものを期待している。

この2つで表現できない木DPが存在したら、そのときはadhocに実装するしかない(同型性判定のハッシュ計算はこれでうまくいくだろうか?あれは難しい)。木DPの構造はまだ整理しきれてないので、よりよい表現が見つかったら追記する。

変更履歴

  • 2017/03/31: コードを修正した。木DPに関する考察を付け加えた。