Oliver and the Game

The problem, simply

A town has N houses joined by N - 1 roads, so there is exactly one way between any two houses. House 1 is the King's castle. Bob hides in house X. Oliver starts at house Y.

Each question has a type. Type 0: Oliver walks from Y toward the castle. Type 1: Oliver walks from Y away from the castle (he may pick any branch). Answer YES if Oliver can find Bob, otherwise NO. Answer Q such questions.

In tree words: type 0 asks "is X on the path from Y up to the root?", which means X is an ancestor of Y (or the same house). Type 1 asks "is X somewhere below Y?", which means Y is an ancestor of X.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write down each house's parent (the next house toward the castle). For each question, climb from the lower house toward the castle and see if you meet the other house.

1. Walk the tree once from house 1 and store parent[v] for every house.
2. For type 0, climb from Y. For type 1, climb from X.
3. If the climb meets the other house, answer YES. If it passes the castle, answer NO.

class OliverClimb {
    public static List<String> solve(int n, int[][] roads, int[][] queries) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int[] r : roads) { adj.get(r[0]).add(r[1]); adj.get(r[1]).add(r[0]); }

        int[] parent = new int[n + 1];                 // parent of the castle stays 0
        boolean[] seen = new boolean[n + 1];
        Queue<Integer> line = new ArrayDeque<>();
        line.add(1);
        seen[1] = true;
        while (!line.isEmpty()) {
            int u = line.poll();
            for (int v : adj.get(u)) {
                if (!seen[v]) { seen[v] = true; parent[v] = u; line.add(v); }
            }
        }

        List<String> answers = new ArrayList<>();
        for (int[] q : queries) {
            int type = q[0], x = q[1], y = q[2];
            int top = type == 0 ? x : y;               // the house that must be higher up
            int cur = type == 0 ? y : x;               // start climbing from the other one
            boolean found = false;
            while (cur != 0) {
                if (cur == top) { found = true; break; }
                cur = parent[cur];
            }
            answers.add(found ? "YES" : "NO");
        }
        return answers;
    }
}

How long it takes: one climb can pass every house when the tree is a long line, so Q questions cost O(N * Q). With N and Q both near 100,000 that is far too slow. Extra room: the parent array, O(N).

Way 2: the clever way

Stamp every house with an in time and an out time during one walk. A house A is above house B (or is B) exactly when in[A] <= in[B] and out[B] <= out[A]. The walk is a depth first search, and the stamps are called entry and exit times.

1. Start a clock at 0. Walk from the castle. When you enter a house, write in and tick the clock.
2. Visit every child fully before leaving. When you leave a house, write out and tick the clock.
3. For type 0, answer isAbove(X, Y). For type 1, answer isAbove(Y, X).

class OliverStamps {
    static int[] in, out;

    public static List<String> solve(int n, int[][] roads, int[][] queries) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int[] r : roads) { adj.get(r[0]).add(r[1]); adj.get(r[1]).add(r[0]); }
        stamp(n, adj);

        List<String> answers = new ArrayList<>();
        for (int[] q : queries) {
            int type = q[0], x = q[1], y = q[2];
            boolean yes = type == 0 ? isAbove(x, y) : isAbove(y, x);
            answers.add(yes ? "YES" : "NO");
        }
        return answers;
    }

    // a is b, or a is on the way from b up to the castle
    static boolean isAbove(int a, int b) {
        return in[a] <= in[b] && out[b] <= out[a];
    }

    // depth first walk with our own pile, so a long line of houses cannot overflow the call stack
    static void stamp(int n, List<List<Integer>> adj) {
        in = new int[n + 1];
        out = new int[n + 1];
        int[] parent = new int[n + 1];
        int[] nextChild = new int[n + 1];
        Deque<Integer> pile = new ArrayDeque<>();
        int clock = 0;
        pile.push(1);
        in[1] = clock++;
        while (!pile.isEmpty()) {
            int u = pile.peek();
            if (nextChild[u] < adj.get(u).size()) {
                int v = adj.get(u).get(nextChild[u]++);
                if (v == parent[u]) continue;          // do not walk back up
                parent[v] = u;
                in[v] = clock++;                       // stamp on the way in
                pile.push(v);
            } else {
                out[u] = clock++;                      // stamp on the way out
                pile.pop();
            }
        }
    }
}

How long it takes: the walk touches every house and road once, O(N), and each question is four comparisons, O(1). Total O(N + Q). Extra room: the stamps, the parent array and the pile, O(N).

Watch out for

• Mixing up the two types. Type 0 checks isAbove(X, Y), type 1 checks isAbove(Y, X).
• X == Y must give YES. Use <=, not <.
• The roads have no direction. Remember the parent, or a seen array, so the walk does not go back up.
• Reading input fast matters on this problem. Use a fast reader in Java.

What interviewers ask next

• Find the lowest common ancestor of two houses. If one is above the other, it is that one. Otherwise jump up with binary lifting until just below the meeting point, O(log N) per question.
• Count the houses in the part below v, counting v itself. It is (out[v] - in[v] + 1) / 2 with this clock, because each of those houses uses two ticks.
• Add a value to every house below v, or sum them. The houses below v form one stretch of the in-time order, so a Fenwick tree or segment tree over that order works.
• What if the roads can change? Then the stamps break. You need heavier tools like link-cut trees or an offline approach.

Remember this

Grown-up words: the town is a rooted tree, the castle is the root, "above" means ancestor, the stamps are entry and exit times (an Euler tour), and the walk pile is the DFS stack.