mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ CodeForces 問題 codeforces.com 解法 さっきの問題とよく似ています。 mayokoex.hatenablog.comまず, 頂点 0 からつながる頂点を列挙します。これが k 個以下だったら impossible です。で, それらの点からスタートして, 0 以外の頂点となるべく連結させていきます。これは, さっきの問題と同じような方法で出来ます(相変わらず (u, v) が繋げないかどうかの判定はたかだか 2 回しかしないので計算量は O(M log M))。あとは判定ですが, 頂点 0 から他の頂点に伸ばす必要のある最低本数が k 以下であれば良いです。これは, さっきの作業で出来た連… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F03%2F21%2F143817" title="IndiaHacks 2016 - Online Edition E. Bear and Forgotten Tree 2 - mayoko’s diary" 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-03-21 14:38:17 rich https://mayokoex.hatenablog.com/entry/2016/03/21/143817 1.0 100%