Centroid Decomposition

A centroid of a tree is defined as a node such that when the tree is rooted at it, no other nodes have a subtree of size greater than $\frac{N}{2}$.

Resources

• https://usaco.guide/plat/centroid?lang=cpp
• https://codeforces.com/blog/entry/81661 by Colin Galen

Related