Company Queries II - Implementation

Here is the LCA implementation using binary lifting:

function companyQueriesII(n, parent, queries):
    LOG = ceil(log2(n))
    up = 2D array of size n x LOG
    depth = array of size n

// Build sparse table
    for i from 1 to n:
        up[i][0] = parent[i]
    for j from 1 to LOG - 1:
        for i from 1 to n:
            if up[i][j-1] != -1:
                up[i][j] = up[up[i][j-1]][j-1]

// Compute depths with BFS from root
    computeDepths()

function lca(a, b):
        if depth[a] < depth[b]:
            swap(a, b)

// Bring a to same depth as b
        diff = depth[a] - depth[b]
        for j from 0 to LOG - 1:
            if diff & (1 << j):
                a = up[a][j]

if a == b:
            return a

// Binary 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 (a, b) in queries:
        print lca(a, b)

Time: $O(n \log n)$ preprocessing, $O(\log n)$ per query. Space: $O(n \log n)$.