AtCoder Grand Contest 001: C. Shorten Diameter

木の中心：他の頂点との距離の最大値が最小になる頂点

解となる木には中心が存在する。最小を与える木が下図のようなものだったとすれば、赤い頂点が中心である。

f:id:pekempey:20160718021531p:plain

中心が分かってしまえば、逆に解となる木を構成することは容易である。中心から（直径）/2より遠い頂点をすべて削除すればいい。

したがって、それぞれの頂点を木の中心だと仮定して構成を試せば必ず解となる木が現れる。これで答えが求まる。

木の中心は直径の偶奇に応じて振る舞いが変わる。直径が偶数のときは中心が 1 つで、直径が奇数のときは中心が 2 つになる。そのため直径が奇数のときは、隣接する 2 頂点が中心だと仮定して構成を試すといい。

木の中心に関しては、以前書いた記事が参考になるかもしれません。

本番では奇数の処理をもっと面倒に考えていたけど、整理するとシンプルだね。