Implementation - Counting Paths - Implement Solution

Here is the path counting implementation:

function countingPaths(n, adj, marked, queries):
    // Preprocess: depths, binary lifting, prefix counts
    depth = array of size n + 1
    up = 2D array of size (n + 1) x LOG
    count = array of size n + 1  // prefix sum of marked nodes

    function dfs(u, parent):
        up[u][0] = parent
        count[u] = count[parent] + (1 if u in marked else 0)
        for v in adj[u]:
            if v != parent:
                depth[v] = depth[u] + 1
                dfs(v, u)

    dfs(1, 0)
    buildBinaryLiftingTable()

    for (u, v) in queries:
        ancestor = lca(u, v)
        parentLca = up[ancestor][0]
        // Nodes on path = count[u] + count[v] - count[lca] - count[parent of lca]
        result = count[u] + count[v] - count[ancestor] - count[parentLca]
        print result

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