The Centroid — Solution & Editorial
Compute subtree sizes; for each node the largest resulting component is max(N−size[u], largest child subtree). The centroid minimizes this maximum.
Complexity: O(N)
Compute subtree sizes; for each node the largest resulting component is max(N−size[u], largest child subtree). The centroid minimizes this maximum.
Complexity: O(N)