Distance Queries - Analysis

For each node $v$, store $dist[v][i]$ = distance from $v$ to its $i$-th centroid ancestor. Since centroid tree depth is $O(\log n)$, this takes $O(n \log n)$ space.

Query $(u, v)$: find the lowest centroid $c$ that is an ancestor of both $u$ and $v$ in the centroid tree.

Then: $distance(u, v) = dist[u][c] + dist[v][c]$ To find the common centroid ancestor, walk up from both $u$ and $v$ until you meet. With preprocessing, this takes $O(\log n)$ time.