[백준, BOJ 11438] LCA 2 (java)

https://www.acmicpc.net/problem/11438

11438번: LCA 2

---

문제

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

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

입력

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

출력

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

728x90

 

예제 입력 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;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static ArrayList<ArrayList<Integer>> list;
	static int k;
	static int[] depth;
	static int[][] parent;
	
	private static void getDepth() {
		
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {1, 0});
		
		while(!q.isEmpty()) {
			int[] tmp = q.poll();
			int now = tmp[0];
			int d = tmp[1];
			
			for (int i = 0; i < list.get(now).size(); i++) {
				int next = list.get(now).get(i);
				if(next != 1 && depth[next] == 0) {
					depth[next] = d + 1;
					parent[0][next] = now;
					q.add(new int[] {next, d + 1});
				}
			}
		}
	}
	
	private static void getParent() {
		
		for (int i = 1; i <= k; i++) {
			for (int j = 2; j <= N; j++) {
				parent[i][j] = parent[i - 1][parent[i - 1][j]];
			}
		}
		
	}
	
	private static int lca(int a, int b) {
		// depth가 더 큰 수를 b에 저장
		if(depth[a] > depth[b]) {
			int tmp = a;
			a = b;
			b = tmp;
		}
		
		// b의 조상 중 a와 depth가 같은 조상을 b에 저장
		int sub = depth[b] - depth[a];
		for (int i = k; i >= 0; i--) {
			if(Math.pow(2, i) <= sub) {
				b = parent[i][b];
				sub -= Math.pow(2, i);
			}
		}
		
		// 같은 depth로 올려줬을 때 같은 값이라면 리턴
		if(a == b) return a;
		
		// 공통 조상 중 가장 밑에 있는 조상 바로 밑 구하기
		for (int i = k; i >= 0; i--) {
			if(parent[i][a] != parent[i][b]) {
				a = parent[i][a];
				b = parent[i][b]; 
			}
		}
		
		return parent[0][a];
	}

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		list = new ArrayList<>();
		for (int i = 0; i <= N; i++) {
			list.add(new ArrayList<>());
		}
		
		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list.get(a).add(b);
			list.get(b).add(a);
		}
		
		// 2^k >= N인 k 구하기
		
		for (int i = 0; i <= N; i++) {
			k = i;
			if(Math.pow(2, i) >= N) break;
		}
		
		depth = new int[N + 1];
		parent = new int[k + 1][N + 1];
		
		// 각 노드의 depth와 첫 번째 부모 구하기
		getDepth();
		
		// 각 노드의 2^i 번째 조상 구하기
		getParent();
		
		// M개의 공통 조상 구하기
		int M = Integer.parseInt(br.readLine());
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			sb.append(lca(a, b) + "\n");
		}
		
		System.out.println(sb);
	}
}