木DP. DFSは，葉から決まるので木の問題を解くのに適している． 今いる頂点 \(cu\) に対して， \(ne \in to[cu]\) の結果を集計をどうするかを考える． 今回の問題では，辺と次数が重要なので， \(cu,ne\) を結ぶ辺が影響を与える． 逆に，それ以外の辺は集計に影響を与えない．
DPは全探索であるから，素直に全探索を考えると， \(\,(cu,ne)\) の辺を使うか使わないかで 場合分けになる． まず考えると， \(ne\) から出ている辺のうち，使う本数で場合分けだろうか？ しかし，実際には場合分けはまとめることができる．
辺 \(\,(cu,ne)\) を使う場合は， \(ne\) 以下の subtree において， \(ne\) から出る辺は \(d_{ne}\) 未満になる． 使わない場合は， \(d_{ne}\) 以下になる． それらの答えを \(dp_{<, ne}, dp_{\leq, ne}\) とする． 負のコストの辺があるので，\(d_{ne}\) 本全てを使わないほうが得になるケースがある． ここで，常に\(dp_{<, ne} \leq dp_{\leq, ne}\)が成立することに注意．
次に，\(ne \in to[cu]\) を動かしたときの\(\,(cu,ne)\)の辺は，どれを使えば良いのかを考える． 暫定的に全て \(dp_{\leq, ne}\) としておいて， 辺 \(\,(cu,ne)\) を選んだときに差分 \(e_{ne}\) が増えると考えればよい． つまり， \(e_{ne}\) の大きい順に辺 \(\,(cu,ne)\) を使えばよい． ただし，0以下のコストの辺は使わない方が絶対得．
実装
\(d_{v} = 0\) のとき， \(d_{v}\) 本未満は選べないので， \(dp_{<, v} = - \infty\) となる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
