Centroid decomposition

A recursive decomposition (divide-and-conquer) of a tree into multiple subtrees. This allows performing certain operations involving paths on the original tree effectively, by taking every path on the tree into account exactly once when it passes through the root of a decomposed subtree. The roots of the subtrees are chosen to be centroids so that the recursive decomposition has logarithmic depth.

Sources:

• https://petr-mitrichev.blogspot.com/2015/03/this-week-in-competitive-programming_22.html
• https://github.com/cheran-senthil/PyRival/blob/master/pyrival/graphs/centroid_decomposition.py