ARC083-E Bichrome Tree

dp解けなくて悲しいね...

解法

要するに、「根をそれぞれの色で塗った時の合計がX_i以下になる」を満たせば 頂点に重みをつけることで満たすことができる

じゃあどうやって求めるのか、ということですが...

根をどちらかに塗った時の値は

X_iの値(定義から自明)

片方の色の値

じゃあ、この「片方の色の値」を最小化していけば、

効率のいい塗り方が求められるのでは

となります

この値をdp[i]...(頂点iで片方の色で総和をX_iにした時のもう片方の色の総和)

とすれば

ナップサックで解けますね

たどり着けなくて悲しいね

Submission #2171065 - AtCoder Regular Contest 083