Implementation - Distance Queries - Implement Solution

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: $O(n \log n)$ preprocessing, $O(\log n)$ per query. Space: $O(n \log n)$.