[백준]#11438 LCA 2

문제

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

예제 입력 1

15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 6
8 13
8 15

예제 출력 1

2
4
2
1
3
1

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    static ArrayList<Integer>[] graph;
    static int N;
    static boolean[] visited;
    static int[][] parent;
    static int[] depth;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        depth = new int[N+1];
        parent = new int[N+1][18];
        visited = new boolean[N+1];
        graph = new ArrayList[N+1];

        for(int i=1; i<=N; i++)
            graph[i] = new ArrayList<>();

        for(int i=0; i<N-1; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);

            graph[a].add(b);
            graph[b].add(a);
        }

        dfs(1, 0);
        make_tree();

        int M = Integer.parseInt(br.readLine());
        for(int i=0; i<M; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);

            if(depth[a]<depth[b]) {
                sb.append(lca(b, a)+"\n");
            }

            else {
                sb.append(lca(a, b)+"\n");
            }

        }

        System.out.print(sb);
    }

    static int lca(int a, int b) {

        int diff = depth[a] - depth[b];

        for(int i=0; diff>0; i++) {
            if((diff|1)==diff) {
                a = parent[a][i];
            }
            diff >>= 1;
        }

        if(a==b) return a;
        
        for(int i=17; i>=0; i--) {
            if(parent[a][i]!=parent[b][i]) {
                a = parent[a][i];
                b = parent[b][i];
            }
        }

        return parent[a][0];
    }

    public static void make_tree(){
        for(int j=1; j<18; j++){
            for(int i=1; i<=N; i++){
                parent[i][j] = parent[parent[i][j-1]][j-1];
            }
        }
    }

    public static void dfs(int temp, int d){
        visited[temp] = true;
        depth[temp] = d;

        for(int next : graph[temp]){
            if(!visited[next]){
                parent[next][0] = temp;
                dfs(next, d+1);
            }
        }
    }
}