hewla https://blog.hatena.ne.jp/hewla/ Hewlaの競プロ記 https://hewla.hatenablog.com/ 解説 500点です。 問題リンク結局何を求めればいいのかの考察はすぐ終わりましたが、それをどう実装するのかでそれなりに詰まりました。 解説 「子孫へ有向辺を引く」とあります。このことから、新しい辺を引くことによって、根からその頂点への最短距離は短くなった、ということが言えます。つまり、各頂点への最長経路で通る辺が元の木というわけです。 これを実装します。トポロジカルソートを用いた解法がわかりやすくてよいと聞きましたが、今回は自分が採用したBFS(幅優先探索)を用いた解法を解説します。トポロジカルソートは名前しか知りませんでした。 最長経路の探索はよくわかりませんが、最短経路ならできます。辺に重みがな… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fhewla.hatenablog.com%2Fentry%2F2019%2F01%2F27%2F231121" title="Restore the Tree - AtCoder 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 D - Hewlaの競プロ記" 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 2019-01-27 23:11:21 rich https://hewla.hatenablog.com/entry/2019/01/27/231121 1.0 100%