BOJ 11438: LCA 1/2

작성일

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

  • 2월동안 187문제 풀기(지난달 누적 87개) (21/187)
  • 처음 풀어본 LCA
  • dfs와 Binary Lifting을 이용하는 방법.
  • 둘다 똑같은 답 내면 날로먹는것 같으니.. 파이썬으로도 풀어보자.
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
#include <bits/stdc++.h>
using namespace std;

const int SZ = 100001;
int depth[SZ], visit[SZ], par[SZ][21];
vector<int> adj[SZ];
int N, M, a, b;

void input() {
  scanf("%d", &N);
  for(int i = 0; i < N-1; i++) {
    scanf("%d%d", &a, &b);
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
}

void dfs(int n, int d) {
  depth[n] = d;
  for(int x : adj[n]) {
    if(depth[x]) continue;
    par[x][0] = n;
    dfs(x, d+1);
  }
}

void fill() {
  for(int i = 1; i < 21; i++)
    for(int n = 1; n <= N; n++)
      par[n][i] = par[par[n][i-1]][i-1];
}

int lca(int a, int b) {
  if(depth[a] > depth[b]) swap(a,b);
  for(int i = 20; i >= 0; i--)
    if(depth[b] - depth[a] >= 1 << i)
      b = par[b][i];
  if(a==b) return a;
  for(int i = 20; i >= 0; i--) {
    if(par[a][i] != par[b][i])
      b = par[b][i], a = par[a][i];
  }
  return par[a][0];
}

int main() {
  input();
  dfs(1, 1);
  fill();
  scanf("%d", &M);
  for(int i = 0; i < M; i++) {
    scanf("%d%d", &a, &b);
    printf("%d\n", lca(a,b));
  }
}