Distance Queries - Implementation

Here's the approach:

function preprocess()
    decompose(0, n)
    for each node v
        walk up centroid ancestors of v
        for each ancestor c at level i
            dist[v][i] := BFS distance from v to c

function query(u, v)
    // Find lowest common centroid ancestor
    ancestorsU := set of centroid ancestors of u
    c := v
    level := centroidLevel[v]
    while c not in ancestorsU
        c := centroidParent[c]
        level := level - 1

    return dist[u][level] + dist[v][level]

Time: $O(n \log n)$ preprocessing, $O(\log n)$ per query.