主食は米

主に競プロ備忘録

ARC 083 E - Bichrome Tree

問題概要

1が根であるN頂点の根付き木が与えられる.
また数列{x_i} (i=1..N) が与えられる.
木に白/黒と非負整数を割り振り,自身を含めた子に含まれる自身と同じ色の頂点の数の総和がx[i]であるようにしたい.
そのように割り振ることはできるか.

解法

実験をして見ると頂点uについて,自身を含むuの子の白/黒の総和は,1つはx[u]であり,
またもう一方は最小化するのが最適であることがわかる.
そのもう一方の数をa[u]と置き,子の集合をC[u]と置こう.
c ∈ C[u] に色を割り振るとは,x[c],a[c]のどちらかを白の総和として,割り振らなかった方を黒の総和として割り振っていくことになる.
a[u]はどちらの色の総和としても構わないので,白の総和だとしよう.
a[u]を最小化するには黒の総和(=Bとする)を最大化して, 自身を黒のx[u]-Bとすれば良い.
この時, a[u] = sum_(c∈C)(x[c]+a[c]) - B となる.
ところで,x[c]/a[c]のいずれか丁度1つを足していった和というのはDPでできる.
特にbitsetを使えば簡単にできて, dp[i] := (iが和としてできるか) として,
初期化 dp[0] = 1
遷移 dp = (dp << x[c]) | (dp << a[c])
でできる.
これを根からDFSして各頂点に対してやっていけば良い.
計算量は毎回O(NX)のDPをしていてO(N2 * X)に見えるが,
実際,各頂点が子としてDPで使われるのは高々1回なのでO(NX)となる.
仮にO(N2 * X)としてもbitsetで1/64になるので十分間に合う.

メモ

どちらかだけ足すDPをすっきり書くのに時間がかかった.

コード