Codeforces Round #774 (Div. 2)

　Cまで三完で終了。

コンテストへのリンク

D. Weight the Tree

　解説AC。木DPでいける。

　木DPはコンテスト中も考えたのだが、goodの頂点の個数を求める部分はそれでいけるけれど、和の最小化の部分が無理な気がして捨ててしまった。……が、普通にいけました。

　ただ、復元部分もちょっと非自明な気がする。「トポロジカルソート順（DPテーブルを作ったときと逆順）に頂点でのDPテーブルを見て、得ならその頂点をgoodにして、その周囲の頂点はgoodにしないと印をつけておく」という方法でいける。よくあるDPの復元のように、遷移を逆に見ている感じではないので、不思議な復元に思えた。