11438번: LCA 2

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


$O(n+m\lg n)$

LCA를 구현하자. sparse table을 이용한다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 100000, LGN = 16;
int n, m;
int dp[MAX_N + 1][LGN + 1], lv[MAX_N + 1];
bool ck[MAX_N + 1];
vector<int> adj[MAX_N + 1];
void dfs(int h) {
    ck[h] = true;
    for (auto it : adj[h]) {
        if (ck[it]) continue;
        lv[it] = lv[h] + 1;
        dp[it][0] = h;
        for (int i = 1; i <= LGN; i++)
            dp[it][i] = dp[dp[it][i - 1]][i - 1];
        dfs(it);
    }
}
int lca(int x, int y) {
    if (lv[x] < lv[y]) swap(x, y);
    for (int i = LGN; i >= 0; i--)
        if (1 << i <= lv[x] - lv[y]) x = dp[x][i];
    if (x == y) return x;
    for (int i = LGN; i >= 0; i--)
        if (dp[x][i] != dp[y][i])
            x = dp[x][i], y = dp[y][i];
    return dp[x][0];
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}