[3176번] 도로 네트워크

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. LCA 알고리즘 :: http://www.crocus.co.kr/660

이 문제는 LCA 알고리즘을 이해하고 어떻게 응용하는지 묻는 문제이다.

이 문제에서 가장 중요한 것은 min, max를 어떻게 가져오나 인데

그것에 대한 해답은 LCA 알고리즘 구현 과정 중에 있다.

LCA는 공통 조상을 찾는 것이고, 그 공통 조상을 찾는 과정에서 같은 깊이로 끌어올리고(서로 다른 두 노드를)

공통 조상을 찾을 때까지 계속 같이 조상 노드를 타고 올라가는 것이다.

make_DP 함수를 보면 알다시피 가장 루트 노드부터 시작하여 리프 노드까지 DP가 쌓인다.

이때 이중 for문이라 의구심이 들 지 모르지만, max_level은 가장 커봤자 16이다. 따라서 전혀 TLE와는 무관하다.

이제 형성된 DP로 LCA와 연동해야 하는데 이때 같은 깊이로 오기 위해 두 노드 중 하나의 노드가 올라오기 시작할 것이다.

그때 그 노드가 올라오면서 DP를 체크하며 min과 max를 가지고 계속 온다.

그리고 두 노드가 깊이가 같아지면 이제 서로 올라가면서 서로의 가중치를 확인하면서 min, max를 구한다.

소스 코드 : 

#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
 
#define swap(a,b){int t = a; a = b; b = t;}
 
#define MAX_NODE 100001
 
using namespace std;
 
typedef pair pii;
 
int depth[MAX_NODE];
int ac[MAX_NODE][20];
 
vector graph[MAX_NODE];
 
int max_level = (int)floor(log2(MAX_NODE));
int maxDP[MAX_NODE][20];
int minDP[MAX_NODE][20];
 
int n;
 
// 트리 형성 알고리즘
void make_tree(int here, int parent, int val)
{
    // 현재 노드의 깊이는 부모 노드 깊이 + 1
    depth[here] = depth[parent] + 1;
 
    // 현재 노드(here)의 2^0 = 1번째 조상은 parent
    ac[here][0] = parent;
    // 현재 노드에서 1번째 조상까지의 min, max DP는 val로 초기화
    minDP[here][0] = val;
    maxDP[here][0] = val;
 
    // i = 1 ~ max_level의 의미는 현재 MAX_NODE가 100000이므로
    // 최대 2^16번 까지 밖에 못 뛴다. 따라서 max_level = 16이고 현재 그것을 의미
    //
    // tmp는 현재 노드의 i-1번째 조상을 의미
    // ac[tmp][i-1]은 현재 노드의 i-1번째 조상의 i-1번째를 의미
    // 결국 현재 노드의 i번째 조상은 이미 쌓여왔던 tmp노드의 i-1번째 조상과 같다.
    for(int i = 1; i <= max_level; i ++)
    {
        int tmp = ac[here][i-1];
        ac[here][i] = ac[tmp][i-1];
    }
 
    // 양방향 그래프에서 there != parent
    // 즉, 아래로 향할 때 자식 노드가 부모 노드로 dfs를 못돌게 하며 단방향 트리로 만든다.
    int len = graph[here].size();
    for(int i = 0; i < len; i ++)
    {
        int there = graph[here][i].first;
        if(there != parent)
            make_tree(there, here, graph[here][i].second);
    }
}
 
// DP 형성 알고리즘
void make_DP()
{
    for(int jump = 1; jump <= max_level; jump++)
    {
        for(int here = 1; here <= n; here ++)
        {
            // tmp는 here의 jump-1번째 조상을 의미한다.
            // minDP[here][jump]는 here의 jump-1까지의 minDP값과 tmp(here의 jump-1번째 조상)의 jump-1번째 조상중 최솟값을 가진다.
            // 리프 노드에서부터 시작하는 것이 아닌 루트 노드부터 시작하기에 DP값이 리프로 갈수록 계속 쌓이는 방향이다.
            int tmp = ac[here][jump-1];
            minDP[here][jump] = min(minDP[here][jump-1], minDP[tmp][jump-1]);
            maxDP[here][jump] = max(maxDP[here][jump-1], maxDP[tmp][jump-1]);
        }
    }
}
 
int main()
{
    scanf("%d", &n);
 
    // 양방향 그래프를 형성
    for(int i = 1; i < n ; i ++)
    {
        int from, to, val;
        scanf("%d %d %d", &from, &to, &val);
 
        graph[from].push_back(pii(to,val));
        graph[to].push_back(pii(from,val));
    }
 
    // 0번 노드는 존재하지 않으니 -1로 설정
    depth[0] = -1;
 
    // 현재 노드, 부모 노드, 현재 노드와 부모 노드 사이의 가중치로
    // tree를 형성
    make_tree(1,0,0);
 
    make_DP();
 
    int k;
    scanf("%d",&k);
 
    while(k--)
    {
        int start, end;
        int ansMin = 987654321, ansMax = -1;
        scanf("%d %d", &start, &end);
 
        if(depth[start] != depth[end])
        {
            // end부분이 start보다 더 깊도록 만들어준다.
            if(depth[start] > depth[end])
                swap(start,end);
 
            for(int i = max_level; i >= 0 ; i --)
                if(depth[start] <= depth[ac[end][i]])
                {
                    // end가 조상을 타고 올라와서 start와 깊이가 같아질 때 까지 반복
                    // 이 과정에서 end의 min, max DP값을 계속 구해나간다.
                    ansMin = min(ansMin, minDP[end][i]);
                    ansMax = max(ansMax, maxDP[end][i]);
                    end = ac[end][i];
                }
        }
 
        int lca = start;
 
        // start와 end의 깊이는 같으나 현재 조상 노드로 가지 못한 경우
        // 서로 노드를 조상 노드를 타고 올라가서 노드가 같아질 때 까지 반복한다.
        if(start != end)
        {
            for(int i = max_level; i >= 0; i --)
            {
                if(ac[start][i] != ac[end][i])
                {
                    // 서로 노드를 타고 올라가면서 현재 존재하는
                    // 그리고 start, end 각각의 방향에 존재하는 dp의 min및 max를 구한다
                    ansMin = min(ansMin, min(minDP[start][i], minDP[end][i]));
                    ansMax = max(ansMax, max(maxDP[start][i], maxDP[end][i]));
                    end = ac[end][i];
                    start = ac[start][i];
                }
 
                lca = ac[start][i];
            }
        }
 
        // start와 lca가 같은 경우 즉, start가 end의 공통조상인 경우를 제외하고
        // lca 바로 아래의 값들까지만 min, max가 설정되어있으므로 start-lca, end-lca사이의 min, max도 구해주어야 한다.
        if(start != lca)
        {
            ansMin = min(ansMin, min(minDP[start][0], minDP[end][0]));
            ansMax = max(ansMax, max(maxDP[start][0], maxDP[end][0]));
        }
        printf("%d %d\n", ansMin, ansMax);
    }
 
    return 0;
}
//                                                       This source code Copyright belongs to Crocus//                                                        If you want to see more? click here >>