최소 공통 조상(LCA : Lowest Common Ancestor)

1. 트리 깊이를 구할 K값을 구함

2. 깊이를 저장할 배열 depth

3. 깊이에 따른 조상값을 저장할 배열 par

4. 간선정보 저장

5. 완전탐색(bfs 등)을 통하여 depth, par 배열 갱신

6. 조상배열(par) 을 깊이에 따라 갱신 par[i][j] = par[i-1][par[i-1][j]];

7. 문제에 따른 lca(a, b)수행

1) a를 depth가 더 깊도록 swap

2) a, b의 높이 차이 계산 diff

3) diff를 2진법으로 변환하여 a값을 갱신

4) a 와 b의 값이 동일하면 a를 return

5) 다르면 K보다 1개 작은 차수부터 부모차수까지 이동하면서 값 갱신

6) a의 부모 (par[0][a]) 값이 lca

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	/*
	 * LCA2
	 * https://www.acmicpc.net/problem/11438
	 */

	static int K = 0;
	static int[][] par;
	static int[] depth;
	static ArrayList[] adjList;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		
		//K max값 구하기
		for (int i = N; i >= 1; i/=2, K++); 		
		
		//초기화, 0부터 필요
		depth = new int[N+1];
		par = new int[K+1][N+1];
		adjList = new ArrayList[N+1];
		for (int i = 0; i <= N; i++) { 				
			adjList[i] = new ArrayList();
			depth[i] = -1;
		}
		
		//데이터 입력. 간선노드 만들기
		for (int i = 1; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			adjList[a].add(b);			
			adjList[b].add(a);
		}
		
		//bfs 탐색등으로 depth, par 테이블 채우기
		bfs(1);
		
		//par테이블 채우기(K 승)
		
		for (int i = 1; i <= K; i++) {
			for (int j = 1; j <= N; j++) {
				par[i][j] = par[i-1][par[i-1][j]];
			}
		}
		
		int M = Integer.parseInt(br.readLine());
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			int result = lca(a, b);
			bw.write(result+"\n");
		}		
		
		br.close();
		bw.flush();
		bw.close();
	}
	
	
	static int lca(int a, int b) {
		//depth 가 a가 더 낮으면 더 깊은것으로 swap
		if(depth[a] < depth[b]) {
			int tmp = a;
			a = b;
			b = tmp;
		}
		
		//높이 차이 계산
		int diff = depth[a] - depth[b];

		//ex) diff = 11
		// 11 = 2^3 + 2^1 + 2^0
		int k = 0;
		while (diff >= 1) {
			if (diff%2 == 1) {
				a = par[k][a];
			}
			
			diff /= 2;
			k++;
		}
		
		//위로 올라가 b와 동일한 값이 나오면 a는  LCA 임
		if (a == b) {
			return a;
		}
		
		//남은 부분은 남은 값으로 점프
		for (k = K-1; k > -1; k--) {
			if (par[k][a] != par[k][b]) {
				a = par[k][a];
				b = par[k][b];
			}
		}
		
		return par[0][a];
	}
	
	static void bfs(int root) {
		
		Queue que = new LinkedList();
		que.add(root);
		
		// 최초 시작점의 부모는 0
		par[0][root] = 0;
		
		while(!que.isEmpty()) {
			int cur = que.poll();
			for (int next : adjList[cur]) {
				
				//다음점 값과 현재나온값의 부모값이 동일하면 continue. 양방향 노드여서 부모자식간 값이 같을 수 있음
				if(next == par[0][cur]) {
					//System.out.println(next+" "+par[0][cur]);
					continue;
				}
				
				//다음노드 깊이는 부모노드+1
				depth[next] = depth[cur] + 1;
				
				//다음노드의 부모값은 현재값;
				par[0][next] = cur;
				que.add(next);				
			}
		}
	}
}