Given a tree with nodes and queries, answer distance queries: what is the distance (number of edges) between nodes and ? Constraints: .
This you can solve with LCA, but centroid decomposition offers an alternative approach that extends to harder variants.
The idea: precompute distances from every node to all its centroid ancestors. Query finds their lowest common centroid ancestor and combines distances.