###### tags: `解説`

# [宝探し](https://onlinejudge.u-aizu.ac.jp/beta/room.html#HUPC2021Day2/problems/F) 解説

結論から言うと
$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テーブルを更新することができます。