BOJ. Lowest Common Ancestor (3584)

[Link] https://www.acmicpc.net/problem/3584

Each test case gives a rooted tree with N nodes and exactly one pair of nodes whose lowest common ancestor (LCA) must be found. The input edges are directed from parent to child, so store each child’s parent in a parent array. The one node with no parent is the root.

For the query, mark the first node and each of its ancestors by repeatedly following parent links. Then start at the second node and climb toward the root until reaching a marked node. The first marked node encountered is the lowest common ancestor: every node on the second node’s upward path is an ancestor of it, and the first intersection with the first node’s ancestor chain is the deepest shared ancestor. This includes queries where one queried node is itself an ancestor of the other, including the root.

Building parent takes O(N) time. Marking and climbing take at most O(N) time in total, using O(N) space. The algorithm is iterative, so a tree shaped as a chain of 100,000 nodes does not consume the call stack.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder output = new StringBuilder();
        int testCases = Integer.parseInt(input.readLine().trim());

        for (int test = 0; test < testCases; test++) {
            int n = Integer.parseInt(input.readLine().trim());
            int[] parent = new int[n + 1];
            for (int edge = 0; edge < n - 1; edge++) {
                StringTokenizer tokens = new StringTokenizer(input.readLine());
                int from = Integer.parseInt(tokens.nextToken());
                int to = Integer.parseInt(tokens.nextToken());
                parent[to] = from;
            }

            int root = 1;
            while (parent[root] != 0) {
                root++;
            }

            StringTokenizer query = new StringTokenizer(input.readLine());
            int first = Integer.parseInt(query.nextToken());
            int second = Integer.parseInt(query.nextToken());

            boolean[] ancestors = new boolean[n + 1];
            for (int node = first; ; node = parent[node]) {
                ancestors[node] = true;
                if (node == root) {
                    break;
                }
            }
            while (!ancestors[second]) {
                second = parent[second];
            }
            output.append(second).append('\n');
        }

        System.out.print(output);
    }
}