重心(Centroid)
説明
木の重心を列挙する。
木の重心は $2$ つか $1$ つあり, $2$ つあるときは両方の部分木の大きさが $N/2$, $1$ つあるときはその頂点の部分木の大きさが $\frac {(N-1)} {2}$ 以下となる。
計算量
$O(N)$
実装例
木の重心を列挙する。
木の重心は $2$ つか $1$ つあり, $2$ つあるときは両方の部分木の大きさが $N/2$, $1$ つあるときはその頂点の部分木の大きさが $\frac {(N-1)} {2}$ 以下となる。
$O(N)$