Centroid Decomposition — Divide Trees for Path Problems

Finding centroid

int findCentroid(int u, int p, int treeSize) {
  for (int v : children[u]) if (v != p && subtreeSize[v] > treeSize / 2)
    return findCentroid(v, u, treeSize);
  return u;
}

Recursion

Find centroid c. Answer queries involving paths through c. Recurse on each subtree separately.

Depth O(log N)

Each recursion halves component size. Centroid tree has O(log N) height.

Applications

'Count pairs with distance ≤ K'. Kth ancestor queries. Many path-based problems.