Medium · DFS Entry and Exit Times
Understand → Visualise → Practice.
For each `[a,b]`, return whether a is an ancestor of b, counting a node as its own ancestor.
A DFS gives every node an entry time and an exit time. Node a is an ancestor of b exactly when b's entry time falls inside a's [entry, exit) window.
Use the parent array to list each node's children, with node 0 as the root.
Run one DFS. Record a counter when you enter a node, and the counter's value after all its descendants are finished as its exit time.
For each [a, b], return tin[a] ≤ tin[b] < tout[a]. Every query is O(1) after the single DFS.
O(n + q) time and O(n) space.
Remember a node counts as its own ancestor, so the comparison must use ≤ on the left side.
Read the full guide first: Fenwick Trees and Segment Trees.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.