13116번: 30번
첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1
www.acmicpc.net
사실 링크없이 이문제만 올려놔도 될 정도입니다..
위의 사진처럼 1 ~ 1023까지 perfect binary tree를 구성하고 있습니다.
여기서 a와 b의 최소 공통조상노드를 구하는 문제입니다.
트리는 고정이기때문에 depth와 parent는 입력을 받기전에 미리 구성해줍니다.
우선 dfs로 탐색을 진행하여 노드의 깊이를 저장해줍니다.
dfs로 탐색을 진행하면서 parent[v][0]에 부모노드인 v / 2를 저장합니다.
그 다음 parent배열에 자신의 1, 2, 4, 8, ... (2^N)번째 조상노드를 저장합니다.
입력으로 x, y를 받으면 x와 y의 최소 공통조상노드를 구합니다.
우선 y의 깊이가 더 크게 맞춰놓고
y의 깊이를 x에 맞춰줍니다.
그 다음 x와 y의 조상이 같아질때까지
x = parent[x][i]
y = parent[y][i]
연산을 반복합니다.
최종적으로 parent[x][0]을 출력해줍니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static int depth[] = new int[1024];
static int parent[][] = new int[1024][11];
static void dfs(int v, int d) {
depth[v] = d;
parent[v][0] = v / 2;
int next = v * 2;
if (next >= 1024)
return;
dfs(next, d + 1);
dfs(next + 1, d + 1);
}
static void init() {
dfs(1, 1);
for (int j = 1; j < 11; j++) {
for (int i = 1; i <= 1023; i++) {
parent[i][j] = parent[parent[i][j - 1]][j - 1];
}
}
}
static int lca(int x, int y) {
if (depth[x] > depth[y]) {
int tmp = x;
x = y;
y = tmp;
}
for (int i = 10; i >= 0; i--) {
if (depth[y] - depth[x] >= (1 << i)) {
y = parent[y][i];
}
}
if (x == y)
return x;
for (int i = 10; i >= 0; i--) {
if (parent[x][i] != parent[y][i]) {
x = parent[x][i];
y = parent[y][i];
}
}
return parent[x][0];
}
static void input() throws Exception {
int u, v;
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
sb.append(lca(u, v) * 10 + "\n");
}
public static void main(String[] args) throws Exception {
init();
st = new StringTokenizer(br.readLine());
int tc = Integer.parseInt(st.nextToken());
while (tc-- > 0) {
input();
}
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > LCA' 카테고리의 다른 글
| boj 1626 두 번째로 작은 스패닝 트리 (0) | 2021.04.02 |
|---|---|
| boj 15481 그래프와 MST (0) | 2021.04.01 |
| boj 15480 LCA와 쿼리 (0) | 2021.02.14 |
| boj 11438 LCA 2 (0) | 2021.02.11 |
| boj 11437 LCA (0) | 2021.02.11 |