[백준 3176] 도로 네트워크

 

 희소 배열 및 LCA(Lowest Common Ancestor, 최소공통조상) 문제. 

 

 N개의 도시와 그 도시를 연결하는 N-1개의 도로가 있고, 모든 도시 쌍을 연결하는 경로가 유일하게 존재한다. 따라서 이는 트리 형태의 그래프임을 짐작할 수 있다. N이 최대 100,000이 들어오고, K가 최대 100,000이므로 매번 일반적인 방법으로 그래프 탐색을 진행하면 시간 초과가 발생할 것이다.

 따라서 캐싱된 데이터를 마련할 필요가 있음을 추측할 수 있고, 하지만 모든 도시 연결 쌍에 대해 미리 경로 상의 가장 긴 도로와 가장 짧은 도로를 구하는 것은 불가능하다. 도시가 100,000개인 경우, 100,000 * (100,000-1) 개의 도시 쌍이 존재하고 도시 쌍마다 4 Bytes 정수 두 개가 필요하다. 출발지와 목적지를 구분 없이 사용한다고 해도 절반 밖에 줄어들지 않으므로 이는 메모리를 초과할 수밖에 없다. 물론, 시간 복잡도 상으로도 불가능하다.

 

 다음으로 생각해 볼 수 있는 것은, LCA와 희소 배열을 사용하는 것이다. 주어지는 두 노드의 LCA를 알아내고, 미리 저장해 둔 그 LCA까지의 최장 도로와 최단 도로를 쿼리해 최종적인 경로 상의 최장, 최단 도로를 알아낼 수 있다. 다만, LCA만 이용한다면 모든 경로 상의 캐싱된 데이터를 만드는 것과 다를 바가 없다. 그래서 희소 배열을 이용해, 공간 복잡도를 줄이고 처음 캐싱 테이블을 만드는 시간 복잡도도 줄인다. N개의 노드에 대해 log N번의 연산이 필요하고(O(N logN)), 필요한 메모리도 O(N logN) 선이므로 이는 충분하다. 이후 생성된 테이블을 이용해 K번의 쿼리를 처리하더라도 O(K logN)이므로, 제시간 안에 동작할 것이다.

 

 이후에는 평범하게 희소 배열 초기화 과정에서 2^x번째 조상에 대한 최장, 최단 도로를 둘 다 비교 및 저장해 가며 초기화해 주면 된다. 쿼리도 일반적인 희소 배열 이용 LCA 문제와 다를 바 없이, 깊이가 더 깊은 노드의 높이를 올려 맞춰주고 LCA를 탐색하며 그 과정에서 최장, 최단 도로를 찾아준다. 그리고 각각의 LCA까지의 최장, 최단 도로 값을 비교해 최종적인 쿼리 답을 출력해 주면 끝이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cmath>

using namespace std;

int sparseTable[100001][18][3]; // {nodeNum, max, min}
int depthArr[100001];
vector<vector<pair<int, int> > > dist;
int n, depth;

void initSparseTable() {
    vector<bool> isVisited(n + 1, false);
    stack<pair<int, int> > st;
    st.push({ 1, 1 });

    while (!st.empty()) {
        int curNode = st.top().first;
        int curDepth = st.top().second;
        st.pop();

        if (isVisited[curNode]) continue;
        isVisited[curNode] = true;
        depthArr[curNode] = curDepth;

        for (auto edge : dist[curNode]) {
            if (!isVisited[edge.first]) {
                st.push({ edge.first, curDepth + 1 });
                sparseTable[edge.first][0][0] = curNode;
                sparseTable[edge.first][0][1] = sparseTable[edge.first][0][2] = edge.second;
            }
        }
    }
}

void makeSparseTable() {
    initSparseTable();

    depth = log2(n) + 1;
    for (int i = 1; i <= depth; i++) {
        for (int j = 1; j <= n; j++) { // 탐색 기준 노드
            int parent = sparseTable[j][i - 1][0];
            int anc = sparseTable[parent][i - 1][0];
            sparseTable[j][i][0] = anc;

            if (anc == 0) continue;

            int parentMax = sparseTable[j][i - 1][1];
            int parentMin = sparseTable[j][i - 1][2];

            int ancMax = sparseTable[parent][i - 1][1];
            int ancMin = sparseTable[parent][i - 1][2];

            sparseTable[j][i][1] = max(parentMax, ancMax);
            sparseTable[j][i][2] = min(parentMin, ancMin);
        }
    }
}

pair<int, int> query(int v1, int v2) {
    if (depthArr[v1] < depthArr[v2]) {
        swap(v1, v2);
    }
    int maxCost = 0;
    int minCost = 987654321;

    for (int i = depth; i >= 0; i--) {
        if (depthArr[v1] - depthArr[v2] >= (1 << i)) {
            maxCost = max(sparseTable[v1][i][1], maxCost);
            minCost = min(sparseTable[v1][i][2], minCost);

            v1 = sparseTable[v1][i][0];
        }
    }

    if (v1 == v2) {
        return { maxCost, minCost };
    }

    for (int i = depth; i >= 0; i--) {
        if (sparseTable[v1][i][0] != sparseTable[v2][i][0]) {
            maxCost = max(max(sparseTable[v1][i][1], sparseTable[v2][i][1]), maxCost);
            minCost = min(min(sparseTable[v1][i][2], sparseTable[v2][i][2]), minCost);

            v1 = sparseTable[v1][i][0];
            v2 = sparseTable[v2][i][0];
        }
    }
    maxCost = max(max(sparseTable[v1][0][1], sparseTable[v2][0][1]), maxCost);
    minCost = min(min(sparseTable[v1][0][2], sparseTable[v2][0][2]), minCost);

    return { maxCost, minCost };
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    dist = vector<vector<pair<int, int> > >(n + 1);
    int v1, v2, c, k;
    for (int i = 0; i < n-1; i++) {
        cin >> v1 >> v2 >> c;

        dist[v1].push_back({ v2, c });
        dist[v2].push_back({ v1, c });
    }

    makeSparseTable();

    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> v1 >> v2;
        auto result = query(v1, v2);

        cout << result.second << " " << result.first << "\n";
    }

}