[백준]도로 네트워크(3176)

문제 링크 : [백준]도로 네트워크(3176)

3176번: 도로 네트워크

문제 설명

N개의 도시와 N-1개의 도로가 있고, 모든 도로가 서로 이어져 있을 때, 두 도로가 주어지면, 두 도시를 연결하는 도로 중 가장 긴 도로와 가장 짧은 도로를 출력하세요.

입력

N(도로의 갯수, 1 <= N <= 100,000)

A_i B_i C_i(연결 된 두 도시와 거리, A_i B_i : 연결된 두 도시 번호, C_i : 도로의 길이, 1 <= C_i <= 1,000,000)

M(쿼리의 갯수, 1 <= M <= 100,000)

A_i B_i(두 도시의 번호)

5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2

 

출력

100 200
50 150
50 100

 

카테고리

#LCA

 

시간 복잡도 상한

O(MlogN)

 

해결 방법

1. 모든 도시가 연결 되어 있고, N-1개의 엣지로 이어지려면 트리로 구성되어야만 합니다.
2. 트리에서 두 노드를 잇는 경로 중 최댓값과 최솟값을 찾아야 합니다.
3. 두 노드의 경로는 각 노드에서 최저 공통 조상까지의 경로와 같습니다.
4. 그 경로들 중 최솟값과 최댓값을 구하면 되는데, Sparse table을 이용하여, 공통 부모, 최댓값, 최솟값을 구성하여 원하는 값들을 출력합니다.

시간복잡도

O(Mlog(N))

코드

#include<cstdio>
#include<vector>
#include<limits.h>
#define MAX 100001
int max(int a,int b){
    return a>b?a:b;
}
int min(int a,int b){
    return a>b?b:a;
}
using namespace std;
int n,m,a,b,c,i,j,lca[MAX][21][3],l[MAX];
vector<pair<int,int> > v[MAX];
void dfs(int p,int f){
    for(int i=0;i<v[p].size();i++){
        pair<int,int> c=v[p][i];
        if(c.first==f)continue;
        l[c.first]=l[p]+1;
        lca[c.first][0][0]=p;
        lca[c.first][0][1]=lca[c.first][0][2]=c.second;
        for(int j=1;j<21;j++){
            lca[c.first][j][0]=lca[lca[c.first][j-1][0]][j-1][0];
            lca[c.first][j][1]=min(lca[lca[c.first][j-1][0]][j-1][1],lca[c.first][j-1][1]);
            lca[c.first][j][2]=max(lca[lca[c.first][j-1][0]][j-1][2],lca[c.first][j-1][2]);
        }
        dfs(c.first,p);
    }
}
pair<int,int> find(int a,int b){
    pair<int,int> r;
    r.first=INT_MAX;
    r.second=0;
    if(l[a]>l[b])swap(a,b);
    for(int i=20;i>=0;i--){
        if((1<<i)<=l[b]-l[a]){
            r.first=min(r.first,lca[b][i][1]);
            r.second=max(r.second,lca[b][i][2]);
            b=lca[b][i][0];
        }
    }
    if(a==b)return r;
    for(int i=20;i>=0;i--){
        if(lca[a][i][0]!=lca[b][i][0]){
            r.first=min(r.first,min(lca[b][i][1],lca[a][i][1]));
            r.second=max(r.second,max(lca[b][i][2],lca[a][i][2]));
            a=lca[a][i][0],b=lca[b][i][0];
        }
    }
    r.first=min(r.first,min(lca[b][0][1],lca[a][0][1]));
    r.second=max(r.second,max(lca[b][0][2],lca[a][0][2]));
    return r;
}
int main(){
    scanf("%d",&n);
    for(i=1;i<n;i++){
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    dfs(1,0);
    scanf("%d",&m);
    while(m--){
        scanf("%d%d",&a,&b);
        pair<int,int> x=find(a,b);
        printf("%d %d\n",x.first,x.second);
    }
}