Here is the implementation with edge case handling:
function solve(n, edges, queries):
// Preprocess tree
buildTree(edges)
computeDepths()
buildBinaryLiftingTable()
function lca(a, b):
if depth[a] < depth[b]:
swap(a, b)
// Lift a to same depth as b
for j from LOG - 1 down to 0:
if depth[a] - (1 << j) >= depth[b]:
a = up[a][j]
if a == b:
return a
// Lift both until they meet
for j from LOG - 1 down to 0:
if up[a][j] != up[b][j]:
a = up[a][j]
b = up[b][j]
return up[a][0]
for (u, v) in queries:
if u == v:
print 0
else:
ancestor = lca(u, v)
print depth[u] + depth[v] - 2 * depth[ancestor]
Time: preprocessing, per query. Space: .