ARC083-E Bichrome Tree
dp解けなくて悲しいね...
解法
要するに、「根をそれぞれの色で塗った時の合計がX_i以下になる」を満たせば 頂点に重みをつけることで満たすことができる
じゃあどうやって求めるのか、ということですが...
根をどちらかに塗った時の値は
X_iの値(定義から自明)
か
片方の色の値
じゃあ、この「片方の色の値」を最小化していけば、
効率のいい塗り方が求められるのでは
となります
この値をdp[i]...(頂点iで片方の色で総和をX_iにした時のもう片方の色の総和)
とすれば
ナップサックで解けますね
たどり着けなくて悲しいね