Subtree Queries - Implementation

Compute Euler tour times with DFS. Build array mapping tin[v] to values. Build segment tree on this array. Pseudocode:

timer := 0

function dfs(v, parent):
    tin[v] := timer
    timer := timer + 1
    for child in adj[v]:
        if child != parent then
            dfs(child, v)
    tout[v] := timer

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

Space complexity is $O(n)$ for the data structures used.