KokiYamaguchi https://blog.hatena.ne.jp/KokiYamaguchi/ Learning Algorithms https://kokiymgch.hatenablog.com/ Atcoder Atcoder Regular Contest 088 F. Christmas Tree F - Christmas Tree 感想 木をいくつかのパスで被覆する、よくありそうな問題です。CSA Flip the Edgesに似ています。 解法 まずパスの両端の次数は奇数でそれ以外は偶数である（それはそう）という性質から、グラフの奇数次の頂点は一つ以上のパスの端っこの点になるはずなので、$A$ の必要条件として、$ A \geq $ (奇数次の頂点数 / $2$ ) が言えます。もう少し考えると、$ A =$ (奇数次の頂点数 / $2$) が言えます。これは葉から順にパスを作っていくことを… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkokiymgch.hatenablog.com%2Fentry%2F2018%2F01%2F16%2F155917" title="Atcoder Regular Contest 088 F. Christmas Tree - Learning Algorithms" 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-01-16 16:13:46 rich https://kokiymgch.hatenablog.com/entry/2018/01/16/155917 1.0 100%