Centroid decomposition is an advanced divide-and-conquer technique on trees. The centroid of the tree is found and marked as "removed", paritioning the tree into subtrees with a size of half of the tree or fewer. This process is repeated until all nodes are marked as removed.
We note that the depth of recursion is O(log N) so there are O(N log N) paths from a centroid to all of the other nodes in its subtree right before it was removed, and that any of the O(N²) original paths in the tree can be formed by concatenting two of the O(N log N) paths from the cenroid.
This is of great convenience for problems querying non-trivial information on all paths of a tree.