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: preprocessing, per query. Space: .