SnackDown 2017 Online Elimination Round 解法案
Black Nodes in Subgraphs (BLACKCOM)
https://www.codechef.com/problems/BLACKCOM/
https://www.codechef.com/viewsolution/14319524
問題
入力でN頂点の木が与えられる。各頂点は白か黒のどちらかの色が塗られている。Q個のクエリに答えよ。
クエリ(b, s) : 頂点数がちょうどs、そのうち黒頂点の数がちょうどbの部分連結グラフは存在するか。yes/noで答えよ。
N <= 5000
Q <= 100000
解法
動的計画法/木DP
全ての頂点について、部分木のdpテーブルを4つ作る。
dp1_min[v][s] := 部分木vに対して、「vを含むサイズsの連結部分グラフ」が含む黒頂点の最小の数 dp1_max[v][s] := 同上の最大の数 dp2_min[v][s] := 部分木vに対して、「vを含まないサイズsの連結部分グラフ」が含む黒頂点の最小の数 dp2_max[v][s] := 同上の最大の数
v=0を根とするとクエリ(s, b)に対する答えは
min(dp1_min[0][s], dp2_min[0][s]) <= b && b <= max(dp1_max[0][s], dp2_max[0][s])
である。
ボトムアップにdpテーブルを作る。(頂点v, vの子w)があるとき、wのテーブルを見てvのテーブルを更新。
sz[v] = 1; EACH (e, G[v]) { for (int i=sz[v]; i>=1; i--) for (int j=sz[*e]; j>=1; j--) { amin(dp1_min[v][i+j], dp1_min[v][i] + dp1_min[*e][j]); amax(dp1_max[v][i+j], dp1_max[v][i] + dp1_max[*e][j]); } REP (j, sz[*e]+1) { amin(dp2_min[v][j], dp1_min[*e][j]); amin(dp2_min[v][j], dp2_min[*e][j]); amax(dp2_max[v][j], dp1_max[*e][j]); amax(dp2_max[v][j], dp2_max[*e][j]); } sz[v] += sz[*e]; }
dp1の更新が二重ループになっているが木全体の計算量はO(N^2)になる。
部分木wのサイズをR、部分木vのすでに見た頂点の数をLとしてN=L+Rのステップ数をもとめる（つまりコード中で、sz[v]==L, sz[*e]==Rのとき）。T(N)上記のdpの計算ステップ数とする。
T(N) >= T(L) + T(R) + L*R
N^2 = (L+R)^2 >= L^2 + R^2 + L*R
よってT(N) = O(N^2)
