BOJ)11438 LCA 2

문제: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씩 구해주면 된다.

#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] >= (1 << 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(1, 0);
    f();
    scanf("%d", &m);
    while (m--) {
        scanf("%d%d", &x, &y);
        printf("%d\n", lca(x, y));
    }
    return 0;
}