백준 11438번: LCA 2 (C++)

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

11438번: LCA 2

---

Solved By: LCA, Sparse Table

 

vertex가 100,000개이고, 쿼리의 수가 100,000개라서 기본적으로 알고 있는 LCA로 다음 문제를 풀었을 때는 O(NM) 시간 초과가 납니다.

Sparse Table을 통해 O(MlogN)으로 줄여서 해당 문제를 풀 수 있습니다.

#include <iostream>
#include <vector>
#define MAX 100001
#define LOG_MAX 17
using namespace std;

int parent[MAX][LOG_MAX];
int level[MAX];
vector<int> adj[MAX];
int n, m;

void dfs(int now, int par){
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        if(next == par) continue;
        
        level[next] = level[now] + 1;
        parent[next][0] = now;
        dfs(next, now);
    }
}

void swap(int *a, int *b){
    int *temp = a;
    a = b;
    b = temp;
}

int lca(int a, int b){
    if(level[a] < level[b]) swap(a, b);
    
    int diff = level[a] - level[b];
    
    // b와 같은 level이 되도록 이동
    for(int i = LOG_MAX - 1; i >= 0; i--){
        if(diff >= 1 << i){
            diff -= (1 << i);
            a = parent[a][i];
        }
    }
    
    if(a != b){
        for(int i = LOG_MAX - 1; i >= 0; i--){
            if((parent[a][i] != 0) && (parent[a][i] != parent[b][i])){
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        
        a = parent[a][0];
    }
    
    return a;
}

int main(){
    cin >> n;
    for(int i = 0; i < n - 1; i++){ // tree has n - 1 edges
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    level[1] = 1;
    dfs(1, 0);
    
    for(int j = 1; j < LOG_MAX; j++){
        for(int i = 1; i <= n; i++){
            parent[i][j] = parent[parent[i][j - 1]][j - 1];
        }
    }
    
    vector<int> res;
    cin >> m;
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        res.push_back(lca(a, b));
    }
    
    for(auto v : res) cout << v << '\n';
    
    return 0;
}