백준 33628 Connect the GSHS

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

 

학교 1년 선배 군대 2주 선배 jjaewon9가 추천해줘서 풀었다. 추천해준 날짜가 5/5였으니 대강 2주 좀 안 걸린 것 같다. 지난 한 주 동안 야간 초소 경계근무를 섰는데, 마지막 근무 때 풀이 내고 오늘 짰다.

 

문제를 요약하면, $N$개의 정점을 트리로 합쳐가는 중에 입력받은 임의의 두 정점 사이의 경로에서 해당 컴포넌트의 최소 번호 정점과 가장 가까운 정점을 구하는 쿼리를 온라인으로 처리하는 문제이다. 최소 번호 정점의 위치는 임의적이고, union-find를 진행하며 컴포넌트의 최소 번호 정점은 쉽게 관리할 수 있다. 따라서 임의의 세 정점이 주어질 때 교차점을 찾는 조금 더 일반적인 문제로 생각해도 무방하다.

 

트리가 모두 만들어진 상태에서 세 정점의 교차점을 찾는 문제는 lca 응용 문제로 잘 알려진 https://www.acmicpc.net/problem/17399 와 동일하며, 케이스워크 등 여러 풀이가 있지만 가장 간단한 방법은 lca(a, b), lca(b, c), lca(c, a) 중 가장 깊이가 낮은 정점을 고르는 것이다. lca를 구하기 위해서는 조상을 관리하는 희소 배열이 필요하니, 트리를 합치는 과정에서 희소 배열을 동적으로 만들어갈 수 있다면 문제를 풀 수 있다.

 

트리에서 주로 사용되는 알고리즘 중 온라인으로 적용시킬 수 있는 방법은 내가 아는 한 small to large뿐이니 이쪽으로 생각해 보자. 두 컴포넌트를 잇는 간선을 추가할 때 부모 정점과 같은 컴포넌트였던 정점들의 조상은 변하지 않으니, 자식 정점이 속한 컴포넌트의 조상만 업데이트해 주면 된다. 정점이 $K$개인 컴포넌트의 조상 배열을 일일이 변경하는 시간복잡도는 $O(K\log N)$이므로, small to large의 논리에 따라 간선을 추가할 때마다 작은 컴포넌트를 자식으로 넣어 주면 $O(N\log^2N)$에 문제를 풀 수 있다.

 

희소 배열이 꼭 필요하다는 사고 없이 small to large만 가지고 생각하느라 한참 삽질했다

 

#include <bits/stdc++.h>
using namespace std;
 
 
int p[18][101010], par[101010], sz[101010], mi[101010], d[101010], N, Q, ans;
int find(int v){
    return par[v] ? par[v] = find(par[v]) : v;
}
void merge(int a, int b){
    a = find(a), b = find(b);
    if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    par[a] = b;
    sz[b] += sz[a];
    mi[b] = min(mi[a], mi[b]);
}
 
vector<int> tree[101010];
void dfs(int v, int bef = -1){
    for (int i = 1; i < 18; i++) 
        p[i][v] = p[i-1][p[i-1][v]];
    for (int i : tree[v]){
        if (i == bef) continue;
        p[0][i] = v;
        d[i] = d[v] + 1;
        dfs(i, v);
    }
}
 
pair<int,int> lca(int a, int b){
    if (d[a] < d[b]) swap(a, b);
    for (int i = 0; d[a] != d[b]; i++){
        if ((d[a] - d[b]) & (1 << i))
            a = p[i][a];
    }
    if (a == b) return {d[a], a};
    for (int i = 17; i >= 0; i--){
        if (p[i][a] != p[i][b])
            a = p[i][a], b = p[i][b];
    }
    return {d[a]-1, p[0][a]};
}
 
int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) mi[i] = i, sz[i] = 1;
    while (Q--){
        int op, a, b;
        cin >> op >> a >> b;
        a ^= ans;
        b ^= ans;
        if (op == 1){
            int pa = find(a), pb = find(b);
            if (sz[pa] > sz[pb]) swap(a, b);
            merge(a, b);
            p[0][a] = b;
            tree[a].push_back(b);
            tree[b].push_back(a);
            d[a] = d[b] + 1;
            dfs(a, b);
        }
        else{
            if (find(a) != find(b)) ans = 0;
            else{
                int m = mi[find(a)];
                ans = max({lca(a, b), lca(b, m), lca(m, a)}).second;
            }
            cout << ans << '\n';
        }
    }
}