BOJ. LCA 2 (11438)

Problem: BOJ 11438 — LCA 2 · 한국어 · 日本語

Root the tree at vertex 1. For each vertex v, store its depth and up[v][j], the ancestor reached by moving 2^j edges upward. The root is its own ancestor at every level. This self-parent convention keeps every table entry valid and makes jumps at the root safe.

The ancestor table is built from up[v][0] = parent[v] and up[v][j] = up[up[v][j - 1]][j - 1]. The number of columns is derived from n; 32 - Integer.numberOfLeadingZeros(n) columns cover every possible depth for positive n.

To find the LCA of a and b, first swap them if necessary so a is the deeper vertex. Lift a by the set bits of the depth difference, bringing both vertices to the same depth. If they now match, that vertex is the LCA. Otherwise, inspect jump sizes from largest to smallest and move both vertices upward whenever their 2^j ancestors differ. Each move keeps them below their common ancestor; after the final step, their immediate parent is the LCA.

The initial traversal uses an explicit stack rather than recursion, so a chain of 100,000 vertices does not consume the Java call stack. Preprocessing takes O(N log N) time and space, and each query takes O(log N) time.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(input.readLine());
        ArrayList<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            String[] edge = input.readLine().split(" ");
            int a = Integer.parseInt(edge[0]) - 1;
            int b = Integer.parseInt(edge[1]) - 1;
            graph[a].add(b);
            graph[b].add(a);
        }

        int levels = 32 - Integer.numberOfLeadingZeros(n);
        int[][] up = new int[n][levels];
        int[] depth = new int[n];
        boolean[] visited = new boolean[n];
        int[] stack = new int[n];
        int top = 0;
        stack[top++] = 0;
        visited[0] = true;
        up[0][0] = 0;

        while (top > 0) {
            int vertex = stack[--top];
            for (int neighbor : graph[vertex]) {
                if (visited[neighbor]) {
                    continue;
                }
                visited[neighbor] = true;
                up[neighbor][0] = vertex;
                depth[neighbor] = depth[vertex] + 1;
                stack[top++] = neighbor;
            }
        }

        for (int j = 1; j < levels; j++) {
            for (int vertex = 0; vertex < n; vertex++) {
                up[vertex][j] = up[up[vertex][j - 1]][j - 1];
            }
        }

        int queryCount = Integer.parseInt(input.readLine());
        StringBuilder output = new StringBuilder();
        for (int i = 0; i < queryCount; i++) {
            String[] query = input.readLine().split(" ");
            int a = Integer.parseInt(query[0]) - 1;
            int b = Integer.parseInt(query[1]) - 1;
            output.append(lca(a, b, depth, up)).append('\n');
        }
        System.out.print(output);
    }

    private static int lca(int a, int b, int[] depth, int[][] up) {
        if (depth[a] < depth[b]) {
            int temp = a;
            a = b;
            b = temp;
        }

        int difference = depth[a] - depth[b];
        for (int j = 0; j < up[0].length; j++) {
            if ((difference & (1 << j)) != 0) {
                a = up[a][j];
            }
        }
        if (a == b) {
            return a + 1;
        }

        for (int j = up[0].length - 1; j >= 0; j--) {
            if (up[a][j] != up[b][j]) {
                a = up[a][j];
                b = up[b][j];
            }
        }
        return up[a][0] + 1;
    }
}