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: preprocessing, per query.