Here is the complete distance queries implementation:
function distanceQueries(n, edges, queries):
// Build adjacency list
adj = adjacency list from edges
// DFS to compute depths and parents
depth = array of size n + 1, all 0
up = 2D array of size (n + 1) x LOG
function dfs(u, parent):
up[u][0] = parent
for v in adj[u]:
if v != parent:
depth[v] = depth[u] + 1
dfs(v, u)
dfs(1, 0)
// Fill binary lifting table
for j from 1 to LOG - 1:
for v from 1 to n:
if up[v][j-1] != 0:
up[v][j] = up[up[v][j-1]][j-1]
for (u, v) in queries:
ancestor = lca(u, v)
dist = depth[u] + depth[v] - 2 * depth[ancestor]
print dist
Time: preprocessing, per query. Space: .