kenkoooo https://blog.hatena.ne.jp/kenkoooo/ 宇宙ツイッタラーXの憂鬱 https://kenkoooo.hatenablog.com/ 競技プログラミング Codeforces 問題 Problem - E - CodeforcesN 個の頂点からなる木がある。2K個の大学があり、それぞれ異なる頂点上にある。K個のペアを作ってペア内の各2頂点の距離の合計を最大化せよ。 解法 ある辺を見た時、ペアの両端がそれぞれ辺の反対側にある方が良い。この考えに基づいて、頂点 v と p を結ぶ辺を見た時に、v 側に d 個の大学、p 側に u 個の大学があるとすると、各ペアの片方の大学は d 個の中に、もう片方の大学は u この中に、出来るだけ含まれている方が良い。よって辺 v-p を見た時、min(d, u) 個のペアの両端が、それぞれ v 側と p 側にあるようにする。すると辺… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkenkoooo.hatenablog.com%2Fentry%2F2016%2F07%2F23%2F043406" title="Codeforces Round #364 Div2 E. Connecting Universities - 宇宙ツイッタラーXの憂鬱" 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 2016-07-23 04:34:06 rich https://kenkoooo.hatenablog.com/entry/2016/07/23/043406 1.0 100%