Oliver and the Game
Problem Statement
Given a rooted tree with N nodes (rooted at node 1), answer Q queries. Each query gives a type, a node X, and a node Y. If type = 0, determine if X lies on the path from the root to Y. If type = 1, determine if Y lies on the path from the root to X.
Example:
- Input: Tree with 5 nodes, edges:
[(1,2),(1,3),(2,4),(2,5)], Query:type=0, X=2, Y=4 - Output:
YES(2 is on the path from root 1 to node 4)
Noob-Friendly Explanation
Imagine a family tree starting from one ancestor (the root). Someone asks you: "Is person X an ancestor of person Y?" If type=0, you check if X is an ancestor of Y. If type=1, you check if Y is an ancestor of X.
To check if A is an ancestor of B, you can use entry and exit times from DFS. If A's entry time is ≤ B's entry time AND A's exit time is ≥ B's exit time, then A is an ancestor of B (B is inside A's subtree).
Approach 1: Brute Force
Intuition
For each query, traverse from Y up to the root (following parent pointers). If we encounter X along the way, then X is on the path from root to Y.
Algorithm
- Build the tree and find parent of each node using BFS/DFS from root.
- For each query:
- If type=0: walk from Y to root. If X is found, answer YES.
- If type=1: walk from X to root. If Y is found, answer YES.
import java.util.*;
public class OliverGameBrute {
public static void solve(int n, int[][] edges, int[][] queries) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
// Find parents using BFS from root (node 1)
int[] parent = new int[n + 1];
Arrays.fill(parent, -1);
boolean[] visited = new boolean[n + 1];
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
visited[1] = true;
parent[1] = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neigh : adj.get(node)) {
if (!visited[neigh]) {
visited[neigh] = true;
parent[neigh] = node;
queue.offer(neigh);
}
}
}
// Answer queries
for (int[] q : queries) {
int type = q[0], x = q[1], y = q[2];
if (type == 1) {
// Check if Y is ancestor of X → swap logic
int temp = x; x = y; y = temp;
}
// Check if X is ancestor of Y
boolean found = false;
int curr = y;
while (curr != 0) {
if (curr == x) { found = true; break; }
curr = parent[curr];
}
System.out.println(found ? "YES" : "NO");
}
}
public static void main(String[] args) {
int n = 5;
int[][] edges = {{1,2},{1,3},{2,4},{2,5}};
int[][] queries = {{0, 2, 4}, {0, 3, 4}, {1, 4, 2}};
solve(n, edges, queries);
}
}Complexity Analysis
- Time Complexity: O(N * Q) - each query walks up to the root, which is O(N) in worst case
- Space Complexity: O(N) - parent array
Approach 2: Optimal (Euler Tour / Entry-Exit Times)
Intuition
Perform a DFS from the root and record entry (in-time) and exit (out-time) for each node. Node A is an ancestor of node B if and only if in[A] ≤ in[B] and out[A] ≥ out[B]. This allows O(1) ancestor queries.
Algorithm
- Run DFS from root, recording in-time and out-time for each node.
- For each query:
- If type=0: check if X is ancestor of Y using in/out times.
- If type=1: check if Y is ancestor of X using in/out times.
- A is ancestor of B if
in[A] ≤ in[B] && out[A] ≥ out[B].
import java.util.*;
public class OliverGameOptimal {
static int timer = 0;
static int[] inTime, outTime;
static List<List<Integer>> adj;
public static void solve(int n, int[][] edges, int[][] queries) {
adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
inTime = new int[n + 1];
outTime = new int[n + 1];
timer = 0;
boolean[] visited = new boolean[n + 1];
dfs(1, visited);
// Answer queries
for (int[] q : queries) {
int type = q[0], x = q[1], y = q[2];
if (type == 0) {
// Is X on path from root to Y? i.e., is X ancestor of Y?
System.out.println(isAncestor(x, y) ? "YES" : "NO");
} else {
// Is Y on path from root to X? i.e., is Y ancestor of X?
System.out.println(isAncestor(y, x) ? "YES" : "NO");
}
}
}
static boolean isAncestor(int u, int v) {
return inTime[u] <= inTime[v] && outTime[u] >= outTime[v];
}
static void dfs(int node, boolean[] visited) {
visited[node] = true;
inTime[node] = timer++;
for (int neigh : adj.get(node)) {
if (!visited[neigh]) {
dfs(neigh, visited);
}
}
outTime[node] = timer++;
}
public static void main(String[] args) {
int n = 5;
int[][] edges = {{1,2},{1,3},{2,4},{2,5}};
int[][] queries = {{0, 2, 4}, {0, 3, 4}, {1, 4, 2}};
solve(n, edges, queries);
}
}Complexity Analysis
- Time Complexity: O(N + Q) - DFS is O(N), each query is O(1)
- Space Complexity: O(N) - for in-time, out-time, and adjacency list