hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://beta.atcoder.jp/contests/summerfes2018-div1/tasks/summerfes2018_d 考察過程 1. 最小パス被覆かな？と一瞬思うが、この方針でいくとWA 2. この方針ではない時に考えられるのは木DPくらい 3. パスの状況も追加で保存しておく必要がありそう 4. 正直、あまり自信はないけど、実装してみると通る 解法 https://beta.atcoder.jp/contests/summerfes2018-div1/submissions/3071026木DPをする dfs(cu) = 頂点cuを根とした部分木を改変して作れる… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2018%2F08%2F25%2F184054" title="木からパスへ (Tree---&gt;path) [Summer Festival Contest 2018 D] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-08-25 18:40:54 rich https://blog.hamayanhamayan.com/entry/2018/08/25/184054 1.0 100%