Oliver and the Game (ancestor check on a rooted tree)
Problem
A tree of houses is rooted at 1 (the King's mansion). For each query (type, X, Y), Bob hides at Y. Type 0: can Oliver reach X by moving towards the root from Y? Type 1: can he reach X by moving away from the root from Y? Answer YES/NO. This reduces to "is X an ancestor of Y?" and can be answered with DFS entry/exit times.
Example 1
Input: edges 1–2, 1–3, 2–6, 2–7, 6–9, 7–8, 3–4, 3–5, 5–10; query (0, 2, 8) Output: YES
8 → 7 → 2 moves towards the root.
Also asked as: Oliver and the Game · Oliver and the Game
Test cases
No automated tests for this problem yet. Use the examples above to check your output.
This problem has no automated tests. Run executes your code and shows what it logs.
View solutionHide solution1 approach
1. Euler tour in/out times
Time O(n + q)Space O(n)
DFS from the king’s node recording in[v] and out[v]. u is an ancestor of v iff in[u] ≤ in[v] and out[v] ≤ out[u]. Each query (who moves toward/away from the king) is then O(1).
function eulerTour(n, adj, root = 1) { const tin = new Array(n + 1).fill(0), tout = new Array(n + 1).fill(0); let timer = 0; const dfs = (u, parent) => { tin[u] = ++timer; for (const v of adj[u]) if (v !== parent) dfs(v, u); tout[u] = ++timer; }; dfs(root, 0); const isAncestor = (u, v) => tin[u] <= tin[v] && tout[v] <= tout[u]; return { isAncestor };}