Implementation - Distance Queries

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