ABC259 F - Select Edges (500)
解説の解法
適当な点からDFSで木を探索する
それぞれの点$ i について$ d_i 個以下の辺の場合の最大値と$ d_i個未満の辺の場合の最大値を求める
それぞれ$ dp_{i0}, dp_{i1}とする
$ d_i個未満の場合のみ辺を追加して親と繋げることが可能
$ d_i = 0の場合は$ d_i個未満の方は$ -\infinになる
それぞれの点$ iで以下を行う
それぞれの子$ jをDFSする
$ dp_{i1} = dp_{i1} + dp_{j0}
$ jを繋げたときのコストの差分$ dp_{j1} + cost - dp_{j0}を求めておく
コストを降順でソート
以下の場合については$ d_i回、未満の場合については$ d_i-1回以下を行う
コストがマイナスなら終了
$ dp_iにコストの差分を追加
根とした点のDPの値が答え