Official

F - Tree Patrolling Editorial by penguinman


与えられる木を適当な頂点を根として根付き木に変換した上で、以下の dp を考えます。

  • \(\text{dp}[i][j][k]:=(\)頂点 \(i\) の部分木に含まれる各頂点について高橋くんを配置するかを決めたとき、\(1\) 人以上の高橋くんに警備された頂点がちょうど \(j\) 個ある場合の通り数。ただし
    • \(k\)\(0\) なら頂点 \(i\) に高橋くんが配置されている
    • \(k\)\(1\) なら頂点 \(i\) に高橋くんは配置されておらず、かつ頂点 \(i\) はどの高橋くんにも警備されていない
    • \(k\)\(2\) なら頂点 \(i\) に高橋くんは配置されておらず、かつ頂点 \(i\)\(1\) 人以上の高橋くんに警備されている
      ものとする。\()\)

上記の dp は愚直に行った場合、部分木どうしの dp をマージする際に \(O(N^2)\) 回の計算を要します。マージ操作は全体で \(N-1\) 回行うことになるため、合計での計算量が \(O(N^3)\) となり、実行時間制限に間に合いません。しかし、頂点数 \(X\) の部分木における dp においては、\(X \lt j\) を満たす \(j\) については無視することができます。これを利用すると、頂点数が \(X\) である部分木と \(Y\) である部分木をマージする際にかかる計算量を高々 \(O(XY)\) まで減らすことができます。

これは一見すると定数倍を改善しているだけのように思えます。しかし、実はこれによって \(N-1\) 回のマージ合計での計算量は本質的に改善されていて、具体的には \(O(N^2)\) となります。

細かな計算量解析の手法には、例えば以下のようなものがあります。

\(N\) 頂点 \(0\) 辺の無向グラフ \(G\) を用意する。木上の頂点 \(i\)\(G\) 上の頂点 \(i\) を対応させる。

頂点数 \(X\) の部分木 \(A\) と頂点数 \(Y\) の部分木 \(B\) をマージする際、\(A\) に含まれる全ての頂点から \(B\) に含まれる全ての頂点に向かって \(G\) 上で無向辺を張る。張られた辺の本数はマージにかかる計算量 \(O(XY)\) と一致する。

全てのマージを終えた後の \(G\) は完全グラフとなっており、その辺数は \(O(N^2)\) である。これは上記の木 dp における合計での計算量と一致する。

実装例 (Python)

以下のように、

  • 頂点 \(i\) に高橋くんがいるか否か
  • 頂点 \(i\)\(1\) 人以上の高橋くんに警備されているか

を独立に添字で持った dp をすることも可能です。

実装例 (C++)

posted:
last update: