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