Oliver and the Game (ancestor check on a rooted tree)

Medium

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.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

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 };
}