[c++] 백준 #3176 LCA : 도로 네트워크 (190828)

< 풀이 >

자신의 i번째 부모를 저장하는 배열을 응용한 문제. 결국 I번째 부모까지 연결한 간선 중에 제일 minimum한 거, 제일 maximum한 거를 배열로 저장한 후 나중에 lca 구하고 d~lca까지 갈 때 minimum, maximum edge 계산, e~lca까지 갈 때 minimum, maximum edge를 계산하는 방식이다. 예전에 어려워서 못풀었는데 풀게 되어서 기쁘다.

 

< 소스 코드 >

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define swap(a,b){int t=a; a=b; b=t;}
#define N_MAX 100010


// 그래프
vector<pair<int, ll>> connections[N_MAX];

// depth :: 노드의 깊이(레벨)
// ac[x][y] :: x의 2^y번째 조상을 의미 : sparse table
// weight[x][y] :: x의 2^y번째 조상까지 가는 데 필요한 weight을 의미 
int depth[N_MAX];
int ac[N_MAX][20];
int mn[N_MAX][20];
int mx[N_MAX][20];
ll weight[N_MAX];

int max_level = (int)floor(log2(N_MAX));

void DFS(int here, int parent, int edge){
    depth[here] = depth[parent] + 1;
    
    // 나의 1번째 조상은 부모
    ac[here][0] = parent;
    //부모까지 가는 데 걸리는 edge의 minimum과 max는 간선
    mn[here][0] = edge;
    mx[here][0] = edge;

    // sparse table update
    for(int i=1; i<=max_level;i++){
        int prev = ac[here][i-1];
        ac[here][i] = ac[prev][i-1];

        mn[here][i] = min(mn[here][i-1], mn[prev][i-1]);
        mx[here][i] = max(mx[here][i-1], mx[prev][i-1]);
    }

    int len = connections[here].size();
    for (int i=0; i<len; i++){
        int next = connections[here][i].first;
        ll w = connections[here][i].second;
        if (next == parent) continue;
        DFS(next, here, w);
    }
}

int get_lca(int c, int d){
    // lca를 구한다
    // 1) 같은 depth까지 끌어 올린다
    if (depth[c] != depth[d]){
        if (depth[c] > depth[d]) swap(c,d); // 항상 depth d가 더 크게
        for(int i=max_level;i>=0;i--){
            if(depth[c] <= depth[ac[d][i]]){
                d = ac[d][i];
            }
        }
    }
    int lca = c;
    // 2) 같은 depth라면 lca를 찾는다
    if (c != d){
        for(int i=max_level; i>=0; i--){
            if (ac[c][i] != ac[d][i]){
                c = ac[c][i];
                d = ac[d][i];
            }
            lca = ac[c][i];
        }
    }
    return lca;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N;
    int a, b, w;
    for (int i=1; i<=N-1;i++){
        cin >> a >> b >> w;
        connections[a].push_back(make_pair(b,w));
        connections[b].push_back(make_pair(a,w));
    }
    // 1번 root의 depth가 0이 되도록 하기 위해서임.
    depth[0] = -1;
    DFS(1,0,0);
    
    int K;
    cin >> K;
    while(K--){
        int d, e;
        cin >> d >> e;
        int lca = get_lca(d,e);
        
        int my_min = INF;
        int my_max = 0;
        int diff_d = depth[d] - depth[lca];
        int diff_e = depth[e] - depth[lca];
        int prev = d;
        for(int i=max_level;i>=0;i--){
            if ((1 << i) <= diff_d){
                diff_d -= (1 << i);
                my_min = min(my_min, mn[prev][i]);
                my_max = max(my_max, mx[prev][i]);
                prev = ac[prev][i];
            }
        }
        prev = e;
        for(int i=max_level;i>=0;i--){
            if ((1 << i) <= diff_e){
                diff_e -= (1 << i);
                my_min = min(my_min, mn[prev][i]);
                my_max = max(my_max, mx[prev][i]);
                prev = ac[prev][i];
            }
        }
        cout << my_min << " " << my_max << '\n';
    }
    return 0;
}