木の重心 - かに

木の重心

頂点$ vが木の重心$ \iff$ vを根とした木において、その子を根とする部分木のサイズがどれも$ \frac{N}{2}未満

適当な頂点を根として木DPをする。子側、親側の隣接頂点それぞれについて、部分木のサイズを判定すればOK。

code: centroid.py

def tree_topological_sort(N, G, r):

R = []

P = -1 * N

deq = deque(r)

while deq:

i = deq.popleft()

R.append(i)

for j in Gi:

if j == Pi: continue

Pj = i

deq.append(j)

return R, P

R, P = tree_topological_sort(N, G, 0)

sub = 1 * N # iを根とする部分木のサイズ

center = 1 * N # 頂点iは重心か？

h = N // 2

for i in R:0:-1:

centeri &= N - subi <= h

sub[Pi] += subi

center[Pi] &= subi <= h