ARC029 D - 高橋君と木のおもちゃ

解法

まず、整数を置く回数は、全体で $\min(M,N)$ 回になります。
葉から見ていき、追い出したい数字が置いてある頂点に数字を置く、という操作を繰り返すことでこれは達成できます。
また、ある数字を追い出したいとき、今置いてある頂点より親にあるものは全て追い出されてしまいます。
これにより、葉の方から追い出すか追い出さないかを決めていけば、何か計算できるかもしれない、ということがわかります。
また、数字を置く回数を決めると、 $t$ は大きいものから貪欲に選べることもわかります。

$dp[i][j] =$ 今見ている頂点が $i$ で、追い出すと決めた頂点が $j$ 個あるとき、残すと決めた数字の総和の最大値

というDPを考えます。
すると、
$dp[i][j] = \max \left( \sum dp[to][k] \right)$ (ただし、 $to$ は $i$ の子、 $1 + \sum k = j$ )
という遷移が成立することがわかります。
例外的に、 $j = 0$ の場合のみ、 $dp[i][0] = \sum dp[to][0] + s_{i}$ となります。
この遷移は、二乗の木DPの形になっているため、計算全体で $O(N^{2})$ となっています。
この計算が終わったら、
$dp[1][i]$ と、 $t$ の上から $i$ 個とったものの和について、最大値を計算することで答えが求まります。