16. LCA, sparse table, 오프라인 쿼리

16.md

0.00MB

0. 복습
1. LCA

두 정점의 깊이를 비교해서 더 깊은 정점을 끌어올린다.

두 정점의 깊이가 같다면 두 정점을 같이 끌어올린다.

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main(){
    int T;  cin >> T;
    while(T--){
        int N; cin >> N;
        int P[10001] = {};
        for(int i=0; i<N-1; ++i){
            int A, B; cin >> A >> B;
            P[B]=A;
        }
        int n1, n2; cin >> n1 >> n2;
        set<int> s;
        while(1){
            s.insert(n1);
            if(P[n1]==0) break;
            n1=P[n1];
        }
        while(1){
            if(s.find(n2) != s.end()){
                cout << n2 << '\n';
                break;
            }
            n2=P[n2];
        }
    }
}

11438번을 보자. 이번엔 방금의 방법으로 하기엔 제한이 너무 크다.

한단계씩 끌어올리지 않고, dp를 이용해 여러 단계씩 끌어올려준다.

dp[i][j] : 정점 j의 2^i번째 부모
dp[i][j] = dp[i-1][dp[i-1][j]]

아래의 코드에선 p가 dp의 역할을 수행한다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> G[100001];
int h[100001];
int p[20][100001]; // j번 정점에서 2^i번째 부모.

void DFS(int n, int prev){
    h[n]=h[prev]+1;
    p[0][n]=prev;
    for(int i=0; i<G[n].size(); ++i){
        int next = G[n][i];
        if(next!=prev){
            DFS(next, n);
        }
    }
}

int LCA(int a, int b){
    if(h[a]<h[b]) swap(a, b); // a의 깊이가 더 깊게.
    int gap = h[a]-h[b];
    for(int i=0; i<20; ++i){
        if(gap&(1<<i)) a=p[i][a];
    }
    //a와 b의 높이가 이제 같아짐.
    if(a==b) return a;
    for(int i=19; i>=0; --i){
        if(p[i][a] != p[i][b]){
            a=p[i][a]; b=p[i][b];
        }
    }
    return p[0][a];
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    for(int i=0; i<N-1; ++i){
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    h[1]=0;
    DFS(1, 0); // 높이 구하기
    for(int i=1; i<20; ++i){ // 2의 20승이 100만을 넘어가기 때문에 충분함.
        for(int j=1; j<=N; ++j){
            p[i][j] = p[i-1][p[i-1][j]];
        }
    }
    int M; cin >> M;
    while(M--){
        int a, b; cin >> a >> b;
        cout << LCA(a, b) << '\n';
    }
}

참고 : 3584, 11438, 11437, 1761, 3176

2. sparse table 희소 배열

아까 dp식의 아이디어를 sparse table이라고 한다. 한국어로는 희소 배열, 또는 희소 테이블.

아까 봤던 dp식을 완료하고 dp를 출력해보면 값이 적혀있는 곳이 몇개 없다.

그래서 희소 배열이라고 부르는 것이다.

참고 : 17435

3. 오프라인 쿼리

온라인 쿼리 : 쿼리가 주어질 때마다 대답해준다.

오프라인 쿼리 : 우선 쿼리를 다 받아 놓고, 정렬, 거꾸로 암튼 어떠한 방식으로 계산 후 출력한다.

참고 : 13306