티스토리 뷰

알고리즘 관련/BOJ

BOJ)11438 LCA 2

JASON 자손9319 2017. 1. 19. 18:46

문제:icpc.me/11438


이 문제는 LCA (BOJ 11437) 의 풀이도 포함한다.


루트의 번호가 1번인 N개의 정점으로 이루어진 트리가 존재할 때 두 노드의 쌍 M이 주어질 때 두 노드의 LCA를 구하는 문제이다.


여기서 LCA(Lowest Common Ancestor)란 직역하면 최소 공통 조상(?) 이다.


즉 트리의 두 노드가 주어졌을 때 서로의 조상을 거슬러올라갔을 때 가장 먼저 만나는 정점이 LCA가 된다.


LCA를 구하는 방법으로 두 노드의 높이(깊이)를 맞춘후에 한칸씩 올라가며 조상이 같아질 때까지 비교하는 방법이 있다.


하지만 이방법은 한번의 쿼리를 처리할 때 O(N)의 시간복잡도를 가지므로 LCA 2문제 같이 M과 N이 10만이면 O(N*M)으로 TLE를 피하기 힘들것이다.


그래서 우리는 각 노드마다 2^k번째 부모를 저장하는 방법을 통하여 O(log N)시간에 쿼리를 처리 할 수 있다.


우선 dfs를 돌면서 각 노드의 1번째 부모와 깊이들을 구해준 후 반복문을 통하여 각 노드마다 2^k번째 부모들을 전부 계산해 놓는다.


2^k번째 부모를 계산하는 방법은 par[here][k]=par[par[here][k-1]][k-1]의 수식으로 계산할 수 있다.


이후 lca를 구할 때 두 노드의 높이차를 2^k씩 빼주어 높이를 맞춰준 후 동시에 부모를 비교하여 공통 조상을 구 할때도 2^k씩 구해주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 100000
using namespace std;
int n, m, par[MAX_N + 1][21], x, y, visited[MAX_N + 1], d[MAX_N + 1];
vector<vector<int>> vt;
void dfs(int here,int depth) {
    visited[here] = true;
    d[here] = depth;
    for (int there : vt[here]) {
        if (visited[there])
            continue;
        par[there][0= here;
        dfs(there, depth + 1);
    }
}
void f() {
    for (int j = 1; j < 21; j++) {
        for (int i = 1; i <= n; i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }
}
int lca(int x, int y) {
    if (d[x] > d[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--) {
        if (d[y] - d[x] >= (<< i)) 
            y = par[y][i];
    }
    if (x == y)return x;
    for (int i = 20; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}
int main() {
    freopen("input.txt""r", stdin);
    scanf("%d"&n);
    vt.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d"&x, &y);
        vt[x].push_back(y);
        vt[y].push_back(x);
    }
    dfs(10);
    f();
    scanf("%d"&m);
    while (m--) {
        scanf("%d%d"&x, &y);
        printf("%d\n", lca(x, y));
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1766 문제집  (0) 2017.01.20
BOJ)2623 음악프로그램  (3) 2017.01.20
BOJ)11438 LCA 2  (0) 2017.01.19
BOJ)4386 Freckles  (0) 2017.01.19
BOJ)4343 Arctic Network  (0) 2017.01.19
BOJ)13325 이진 트리  (1) 2017.01.18
TAG
,
댓글
댓글쓰기 폼