木の重心列挙アルゴリズム - Learning Algorithms
木の重心列挙アルゴリズム English version is available here. 木の重心を列挙するアルゴリズムです。重心の性質をよく知っている方にとっては自明な木$dp$を実装するだけだと思います。 これで $verify$ しています。計算量は $O(n)$ です。 中のアルゴリズムとしては、基本的には各頂点についてその頂点からのびる部分木のサイズがすべて $\cfrac {n}{2}$ 以下であるような頂点を求めているだけです。 では、そのような頂点が $3$ 個以上存在しないことを示しておきます。 まず、重心が $2$ 個あるとき、それらは必ず隣接していることを示します。 仮に以下の画像のように、重心 $u$ と重心 $v$ が存在して、これらが隣接していないと仮定します。すると $u$ と $v$ のパス上には必ず一つ以上の頂点が存在することになります。そのうちの一
