E - Bichrome Tree - AtCoder Regular Contest 083
頂点数Nの木とN個の数列X[i]が与えられる。各頂点に対し、ある非負整数を割り当て、かつ白または黒に塗り分けるとき、次の条件をみたすようにしたい。
条件：頂点i を根とするサブグラフについて、頂点i と同じ色の配下(i自身も含む)のノードに割り当てた数字の和がX[i]になる
この条件を満たせるか？
根から、「子の色と異なる数字の和の最小値」 というものを返すdfsを行う。条件から子の色と同じ数字の和は常にX[子ノード]で固定になる。また、現在見ているノードで条件が達成できるかどうかは、「子の色と異なる数字の和」または「子の色と同じ数字の和＝X[子ノード]」の小さい方を足していったときにX[現在ノード]の値を超えないか(※)、である。
この条件を根まで満たせるようにするには、「子の色と異なる数字の和の最小値」というものをどんどん根に向かって返していって矛盾が起きるかどうか判定すれば良い。
(※)はいわゆる0-1ナップサック問題で、X[現在のノード]に最も近い和(これをyとおく)になるように取ればよい。すると、「現在の色と異なる数字の和」は(※)の数のうち、最大のものの和から、yを引いたものを返せばよい。O(max(N, 頂点次数) * max(X)) 。
