Problem - Distance Queries

Given a tree with $n$ nodes and $q$ queries, answer distance queries: what is the distance (number of edges) between nodes $u$ and $v$? Constraints: $n, q \leq 2 \cdot 10^5$.

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 $(u, v)$ finds their lowest common centroid ancestor and combines distances.