[백준] BOJ 15586 : MooTube (Gold)

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

15586번: MooTube (Gold)

일단 문제 조건을 읽어보자면 아래와 같습니다.

1. MooTube의 유사도는 트리 형태

2. 한 영상에서 다른 영상까지 갈려면 경로가 딱 한 가지 밖에 없음

3. 영상 쌍에 대한 유사도는 경로 중 최소 비용의 간선

4. 쿼리에서는 특정 영상과의 유사도가 k 이상인 영상들이 몇 개나 있는지를 물어봄

그리고 이를 읽고나서 저는 처음으로 들었던 생각은 이 문제가 LCA인가 싶었습니다.
왜냐하면, 어쨌든 두 노드 간의 경로에는 항상 LCA를 거쳐서 지나가야 하므로, LCA를 O(logN)으로 계산하면서 전처리를 하고 쿼리별로 구하는 거 아닐까라는 생각이 들었기 때문입니다.

 

그런데, k 이상인 영상들만 구하는 것도 있고, 영상의 유사도가 결국에는 두 노드들을 전부 잇고 있을 때의 최솟값입니다. 그래서 특정 영상과의 유사도가 k 이상인 영상이 있다면 해당 영상과의 연결된 간선들의 유사도가 모두 k 이상이어야 합니다. 그렇다면 쿼리에서 주어진 k는 k 미만인 간선들을 다 끊는 역할이라고도 생각할 수 있었습니다. 그렇게 하고도 유사도가 k 이상인 영상들은 해당 영상이랑 이어져 있어야 합니다.

 

그러면 이 문제를 다시 정리해보자면 "쿼리에서 주어진 k 미만의 간선들을 모두 끊어두었을 때 특정 영상이랑 연결된 영상들의 개수는 몇 개인가?"라는 문제로 정리할 수 있었고, 이를 k가 큰 순서대로 계산한다면 역으로 간선들을 이어줄 수 있으므로 Offline Query + Union Find 문제라는 결론에 도달할 수 있었습니다. 

 

코드는 아래와 같습니다.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
// Default

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// PBDS

ll p[100001];
ll sz[100001];

ll f(ll n){
    if(p[n] == n) return n;
    return p[n] = f(p[n]);
}

void u(ll a, ll b){
    ll pa = f(a);
    ll pb = f(b);
    if(pa == pb) return;

    if(sz[pa] < sz[pb]){
        ll tmp = pa;
        pa = pb;
        pb = tmp;
    } // Smaller-to-Larger
    p[pb] = pa;
    sz[pa] += sz[pb];
    sz[pb] = 0;
    return;
}

// Union-Find

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll N, Q;
    cin >> N >> Q;
    deque<tuple<ll,ll,ll>> v(N-1);
    vector<tuple<ll,ll,ll>> q(Q);
    vector<ll> ans(Q);
    for(int i =1; i<=N; ++i){
        p[i] = i;
        sz[i] = 1;
    }
    for(int i =0; i<N-1; ++i){
        ll a, b, c;
        cin >> a >> b >> c;
        v[i] = {c,a,b};
    }
    sort(v.begin(), v.end(), greater<tuple<ll,ll,ll>>());

    for(int i =0; i<Q; ++i){
        ll k, v;
        cin >> k >> v;
        q[i]={k,v,i};
    }
    sort(q.begin(), q.end(), greater<tuple<ll,ll,ll>>());
    
    for(int i =0; i<Q; ++i){
        ll k, val, idx;
        tie(k, val, idx) = q[i];

        while(!v.empty()){
            ll c,a,b;
            tie(c,a,b) = v.front();
            if(c >= k) {
                u(a,b);
                v.pop_front();
            }
            else break;
        }

        val = f(val);
        ans[idx] = sz[val];
    }

    for(int i =0; i<Q; ++i){
        cout << ans[i]-1<<"\n";
    }

    return 0;
} // Offline-Query, Union-Find, Smaller-to-Larger

오랜만에 풀어보는 USACO 문제, Offline Query + Union-Find 문제는 재밌었습니다.