Blood Cousins - Implementation

Here is the blood cousins implementation:

function bloodCousins(n, adj, queries):
    // Preprocess
    depth = array of size n
    enter = array of size n  // Euler tour entry time
    leave = array of size n  // Euler tour exit time
    up = binary lifting table

    timer = 0
    function dfs(u, parent):
        enter[u] = timer
        timer = timer + 1
        for v in adj[u]:
            if v != parent:
                depth[v] = depth[u] + 1
                dfs(v, u)
        leave[u] = timer

    dfs(root, -1)
    buildBinaryLifting()

    // Group nodes by depth
    nodesByDepth = map from depth to list of enter times (sorted)

    for (v, p) in queries:
        targetDepth = depth[v] - p
        if targetDepth < 0:
            print 0
            continue

        ancestor = getKthAncestor(v, p)
        if ancestor == -1:
            print 0
            continue

        // Count nodes at targetDepth within ancestor's subtree
        L = enter[ancestor]
        R = leave[ancestor]
        nodes = nodesByDepth[targetDepth]
        count = binarySearchCount(nodes, L, R) - 1  // exclude v
        print count

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