ARC 083 E - Bichrome Tree

• 問題
• AC

頂点$v$が与えられたとき、$v$の部分木で$v$と同じ色の重みの和は$X_v$と決まっているが、もう一方の色の重みの和については割り当て次第である程度動かせるはず。そして、この重みの和は、小さい分には先祖の重みの割り当て方が増えるだけなので、小さければ小さいほど良いはず。

そこで、$f(v)$を次のように定める: 部分木$v$で、$v$と同じ色の重みの和が$X_v$になるように重みを割り当てたときの、もう一方の色の重みの和の最小値。

$f$の漸化式について考える。頂点$v$の子を$c_1, ..., c_k$とする。部分木$c_i$の重みの和は、一方の色が$X_{c_i}$、もう一方の色が少なくとも$f(c_i)$である。つまり、$k$個の部分木の重みの決め方は

$X_{c_1}$	$X_{c_2}$	…	$X_{c_k}$
$f(c_1)$	$f(c_2)$	…	$f(c_k)$

から上下の2択が$k$個あるので$2^k$通り考えられて、一方の色の重みの和を$X_v$以下にするという条件でもう一方の色の重みの和を最小にできれば、その値が$f(v)$である。これはナップサック問題のようなDPで求まる: $g_v(y, z)$を、部分木$c_1, ..., c_y$の一方の色の重みの和が$z$以下であるという条件下でのもう一方の色の重みの和の最小値とする。このとき、$f(v) = g_v(k, X_v)$である。$g_v$の漸化式は次のように書ける:

$g_v(0, z) = 0$

$g_v(y, z) = \min(g_v(y-1, z-X_y)+f(y), \: g_v(y-1, z-f(y))+X_y, \:+\infty)$

途中で$f(v) = +\infty$となったら答えはIMPOSSIBLEである。（ただし、それぞれ$z - X_y \ge 0, z-f(y) \ge 0$でない場合は除いて計算する。また、$v$が子を持たない場合は$f(v) = 0$だが、この計算式のままでも自然に$f(v) = g_v(0, X_v) = 0$となるので特別扱いしなくても書ける。）

計算量について。木のそれぞれの頂点$v$についてDPすることになり、その計算量は${\mathcal O}(vの子の数 \cdot X_v)$である。したがって、全体では${\mathcal O}(N\max_i X_i)$。