[JAVA/백준] 11438번: LCA 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.*;
import java.io.*;
/**
 * @author HEESOO
 *
 */
class Main {
	static ArrayList<ArrayList<Integer>> list;
	static int[] depth;
	static int[][] parent;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		int maxDepth=0;
		int check=1;
		while(check<=n) { // 트리의 깊이 계산
			check<<=1;
			maxDepth++;
		}
		
		list=new ArrayList<>();
		for(int i=0;i<n+1;i++) list.add(new ArrayList<>());
		depth=new int[n+1];
		parent=new int[n+1][maxDepth+1];
		
		for(int i=0;i<n-1;i++) {
			String[] s=br.readLine().split(" ");
			int a=Integer.parseInt(s[0]);
			int b=Integer.parseInt(s[1]);
			list.get(a).add(b);
			list.get(b).add(a);
		}
		dfs(1, 1); // 트리 생성
		setParent(n, maxDepth); // 부모 계산
		
		int m=Integer.parseInt(br.readLine());
		for(int i=0;i<m;i++) {
			String[] s=br.readLine().split(" ");
			int a=Integer.parseInt(s[0]);
			int b=Integer.parseInt(s[1]);
			System.out.println(solve(a, b, maxDepth));
			
		}
	}
	
	
	public static void dfs(int node, int cnt) {
		depth[node]=cnt; // node의 깊이 저장
		for(int n:list.get(node)) { // node와 연결된 곳 중
			if(depth[n]!=0) continue; // 방문한 곳은 패스
			parent[n][0]=node; // n의 첫 번째 부모는 node
			dfs(n, cnt+1); // n으로 이동
		}
	}
	
	public static void setParent(int n, int maxDepth) {
		for(int i=1;i<maxDepth;i++) { // 2^i번째 부모 저장
			for(int j=1;j<=n;j++) {
				parent[j][i]=parent[parent[j][i-1]][i-1];
			}
		}
	}
	
	public static int solve(int a, int b, int maxDepth) {
		if(depth[a]>depth[b]) { // a의 깊이가 b보다 더 작도록
			int temp=a;
			a=b;
			b=temp;
		}
		for(int i=maxDepth-1;i>=0;i--) { // a, b가 같은 깊이가 되도록 설정
			if(depth[a]<=depth[parent[b][i]]) b=parent[b][i];
		}
		
		if(a==b) return a;
		// 다르다면
		for(int i=maxDepth-1;i>=0;i--) { // 같이 깊이를 올리며 
			if(parent[a][i]!=parent[b][i]) {
				a=parent[a][i];
				b=parent[b][i];
			}
		}
		return parent[a][0];
	}
}