JunKobayashi https://blog.hatena.ne.jp/JunKobayashi/ JunKobayashi's Diary https://junkobayashi.hatenablog.com/ 木の直径 double-sweep アルゴリズム学習 基礎から徹底 ※本記事は木の直径に関する基礎事項勉強シリーズ第1本である。次回は以下の記事となる。 junkobayashi.hatenablog.com 競技プログラミングにおける「木の直径」とは一般に以下のように定義される。 頂点集合、辺集合をそれぞれ\(V,E\)とする木\(T\)に属する任意の2頂点\(u,v\)について、この2頂点間の距離を\(d(u,v)\)と表記するとき、\[ \max_{u,v \in V} d(u,v) \] これを求めるためには「double-sweep」と呼ばれる、以下のような流れで処理をするアルゴリズムを利用すると良いことが既に広く知られている（が、納得のいく証明をし… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjunkobayashi.hatenablog.com%2Fentry%2F2025%2F04%2F21%2F000636" title="木の直径に関しての勉強1：double-sweepの正当性 - JunKobayashi&#39;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> https://cdn-ak.f.st-hatena.com/images/fotolife/J/JunKobayashi/20250420/20250420223628.png Hatena Blog https://hatena.blog 2025-04-21 00:06:36 rich https://junkobayashi.hatenablog.com/entry/2025/04/21/000636 1.0 100%