tags: 解説

宝探し 解説

結論から言うと

$dp[i$ を根とした部分木で

$][j$ 個宝を発掘したときに

$]=$ 親に移動させることができる人の最大値(親から人をもらわないといけない場合は負になる)
を求めると解くことができます。

頂点

$i$ のDPテーブルは以下のように求めることができます。

・頂点

$i$ が葉の場合

$a[i]$ と

$b[i]$ の大小を比較し、

$dp[i][0]$ と

$dp[i][1]$ を更新します。

・頂点

$i$ が葉でない場合
　子のDPテーブルを利用して以下のDPを求めます。
　

$dp[$ 子孫で

$i$ 個の宝を発掘していて

$][$ 子孫から

$j$ 人移動してくるときの

$]=$ 人の収支の最大値
その後子孫から移動してきた人数と

$a[i]$ と

$b[i]$ を比較してDPテーブルを更新することができます。