BOJ 3176 lubenica(도로 네트워크)

 

문제 링크 : https://www.acmicpc.net/problem/3176

3176번: 도로 네트워크

 

최소 공통 조상을 \(\log(n)\) 시간 이내로 찾을 수 있도록 해주는 것은 이중 배열 prv 이다.

이 배열은 음이 아닌 정수 k 에 대해 \(2^k\) 만큼 앞의 선조에 대한 정보를 기록하고 있다.

 

prv[i][k] 는 i 번 노드의 \(2^k\) 번째 선조로  prv[i][k]=prv[prv[i][k-1]][k-1] 을 만족한다.

 

도로(간선)에 대한 정보도 같은 요령으로 기록하면 된다.

mn[i][k] 는 i 노드의 \(2^k\) 번째 선조까지의 경로 중 최소인 도로(간선)에 대한 정보를 가진다.

위에서 얻은 관계식과 비슷하게 

 

mn[i][k]=min(mn[i][k-1], mn[prv[i][k-1]][k-1]) 

 

가 성립함을 이해하면 나머지는 routine 이다.

 

#include<bits/stdc++.h>

using namespace std;

int N,K;

vector<pair<int,int>> adj[100001];
int level[100001], prv[100001][18], mn[100001][18], mx[100001][18];

void dfs(int cur, int p, int c){
    prv[cur][0]=p;
    mn[cur][0]=mx[cur][0]=c;
    level[cur]=level[p]+1;
    
    for(auto [nxt, cst] : adj[cur]){
        if(nxt==p) continue;
        dfs(nxt, cur, cst);
    }
}

void func(){
    for(int k=1;k<=17;k++)
        for(int i=1;i<=N;i++){
            prv[i][k]=prv[prv[i][k-1]][k-1];
            mn[i][k]=min(mn[i][k-1], mn[prv[i][k-1]][k-1]);
            mx[i][k]=max(mx[i][k-1], mx[prv[i][k-1]][k-1]);
        }
}

pair<int,int> lca(int u,int v){
    if(level[u]<level[v]) swap(u, v);
    int d=level[u]-level[v];
    
    int m=INT_MAX, M=-INT_MAX;    
    for(int i=0; d>0; i++, d>>=1)
        if(d%2) {
            m=min(m, mn[u][i]), M=max(M, mx[u][i]);
            u=prv[u][i];
        }
    
    if(u==v) return {m, M};
    
    for(int i=17;i>=0;i--){
        if(prv[u][i]==prv[v][i]) continue;
        
        m=min(m, min(mn[u][i], mn[v][i]));
        M=max(M, max(mx[u][i], mx[v][i]));
        u=prv[u][i], v=prv[v][i];
    }
    
    m=min(m, min(mn[u][0], mn[v][0])), M=max(M, max(mx[u][0], mx[v][0]));
    return {m,M};
}

int main(){
    scanf("%d",&N);
    for(int i=0;i<N-1;i++){
        int u,v,c; scanf("%d%d%d",&u,&v,&c);
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }
    
    dfs(1,0,0);
    func();
    
    scanf("%d",&K);
    while(K--){
        int u,v; scanf("%d%d",&u,&v);
        pair<int,int> ans=lca(u,v);
        printf("%d %d\n", ans.first, ans.second);
    }
}