shinchankosen https://blog.hatena.ne.jp/shinchankosen/ 橙になりたいaquarium https://shinchankosen.hatenadiary.jp/ 問題 atcoder.jp 頂点の完全マッチングがあることが保証されている木が与えられる。葉の頂点を つ選んで、同時に消すことを繰り返す。ただし、毎回削除後も常に完全マッチングが存在しなければならない。操作列を一つ出力。 は偶数 解説 本質 重心となる頂点を選び根とします。完全マッチングの条件を無視すると、根を通るように葉の頂点を2つ選んで適当な順番で削除していけばよいです。 完全マッチングの条件を考慮すると、本質なのは「各部分木の頂点数の偶奇」だと思います。 重要な性質があります。 頂点 がある部分木の根のとき、部分木の頂点数が奇数なら、 はそのさらに親とマッチングする。逆に偶数なら親とマッ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fshinchankosen.hatenadiary.jp%2Fentry%2F2024%2F08%2F27%2F170755" title="丸紅プログラミングコンテスト2024（AtCoder Regular Contest 183）D問題-Keep Perfectly Matched 解説 - 橙になりたいaquarium" 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 2024-08-27 17:07:55 rich https://shinchankosen.hatenadiary.jp/entry/2024/08/27/170755 1.0 100%