• Do not confuse with Center of a tree , which is a node $v$ that minimizes the distance to all other nodes: $max_{w \in V} d(v, w)$. This can be found by taking the node that is the middle of a diameter.
• The centroid of a tree is a node such that no child has over floor(n/2) of the vertices in the tree.

§ Algorithm to find centroid of a tree

• Root tree arbitrarily at $r$
• Compute subtree sizes with respect to this root $r$.
• Start from root. If all children of root $r$ have size less than or equal to floor(n/2), we are done. Root is centroid.
• If not, some child $c$ [for child, contradiction ] has size strictly greater than floor(n/2).
• The total tree has $n$ vertices. $c$ as a subtree has greater than floor(n/2)vertices. Thus the rest of the tree (ie, the part under $r$ that excludes $c$) has strictly less than floor(n/2) vertices.
• Let us in our imagination reroot the tree at this child $c$. The childen of $c$ continue to have the same subtree size. The old node $r$, as a subtree of the new root $c$, has size strictly ness than floor(n/2) vertices.
• Now we recurse, and proceed to analyze c.
• This analysis shows us that once we descend from r -> c, we do not need to analyze the edge c -> r if we make c the new candidate centroid.

int sz[N]; // subtree sizesvector<int> es[N]; // adjacency listint go_sizes(int v, int p) {  sz[v] = 1;  for (int w : es[v]) {    if (w == p) { continue; }    go_sizes(w, v);    sz[node] += sz[i];  }}int centroid(int v, int p) {  for (int w : es[v]) {    if (w != p && sz[w] > N/2)      return centroid(w, v);  }  return v;}int main() {  ...  go_sizes(1, 1);  centroid(1, 1);};

• Note that one does not need to write the code as follows:

int centroid(int v, int p) {  for (int w : es[v]) {    int wsz = 0;    if (w == p) {      // size of parent = total - our size      wsz = n - sz[v];    } else {      wsz = sz[w];    }    assert(wsz);    if (wsz > N/2) {      return centroid(w, v);    }  }  return v;}

• This is because we have already established that if p descends into v, then the subtree p [rooted at v] must have less than n/2elements, since the subtree v [rooted at p] has more than n/2 elements.

§ Alternate definition of centroid

• Let the centroid of a tree $T$ be a vertex $v$, such that when $v$ is removed and the graph splits into components $T_v[1], T_v[2], \dots, T_v[n]$, then the value $\tau(v) = \max(|T_v[1]|, |T_v[2]|, \dots, |T_v[n]|)$ is minimized.
• That is, it is the vertex that on removal induces subtrees, such that the size of the largest component is smallest amongst all nodes.

§ Existence of centroid

• If tree has exactly one node, we are done, the centroid is the root.
• Suppose for induction a centroid exists for trees of size $n-1$. We will now prove the existence of a centroid for tree of size $n$.
• Otherwise, if the root has all children whose subtree sizes are at most ceil(n/2), the root is the centroid and we are done.
• Otherwise, the root has one child with subtree size strictly greater than ceil(n/2). There can't be two such children, because their combined size would be 2*ceil(n/2) >= n. This is nonsensical, as the size of the subtrees plus the root node would mean the tree has 2*ceil(n/2) + 1 >= n+1 nodes, a contradiction.
• We recurse into the subtree. The size of the subtree of the child is at least one less than the size of the root, thus we are decreasing on the size of the tree.
• By recursion, we must terminate this process and find a centroid.

§ Equivalence to size definition

§ Centroid decomposition

• If we find the centroids of the subtrees that hang from the centroid, then we decompose the graph into a centroid decomposition .
• Once we find the centroid of a tree, we see that all of its subtrees has size less than ceil(n/2).
• We can now recurse, and find sizes of centroids of these subtrees.
• These subtrees are disjoint, so we will take at most O(n) to compute sizes and whatnot.
• We can do this log(n) many steps since we're halving the size of the subtree each time.
• In total, this implies that we can recursively find centroids to arrive at a "centroid decomposition" of a tree.
• Note that the centroid decomposition of the tree constructs a new tree, which is different from the original tree, sorta how the dominator tree is a different tree from the original tree.