BOJ)3176 도로 네트워크

문제: icpc.me/3176

N개의 도시와 그 도시를 연결하는 N-1개의 도로 네트워크가 있을 때 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력하는 문제이다.

우리는 모든 도시 쌍에는 그 도시를 연결하는 유일한 경로가 있다는데에서 주어진 그래프가 트리임을 유추할 수 있다.

우리는 문제를 해결하기 위하여 LCA를 이용할 것이다.

우리는 LCA를 구할 때 두 도시의 2^i번째 부모를 저장한다. 이 때 우리는 2^i번째 부모를 저장할 뿐만 아니라 

x번째 정점 기준으로 2^i번째 부모까지의 모든 간선중에 최솟값과 최댓값을 같이 저장할 수 있다.

이를 이용하여 쿼리를 처리하면 문제를 해결할 수 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 100000
#define INF 2100000000
using namespace std;
int n, k, par[MAX_N + 1][21], qmax[MAX_N + 1][21], qmin[MAX_N + 1][21], d[MAX_N + 1], visited[MAX_N + 1];
vector<vector<pair<int, int>>>vt;
void dfs(int here, int depth) {
    visited[here] = true;
    d[here] = depth;
    for (auto there : vt[here]) {
        if (visited[there.first])
            continue;
        dfs(there.first, depth + 1);
        par[there.first][0] = here;
        qmin[there.first][0] = there.second;
        qmax[there.first][0] = there.second;
    }
}
void f() {
    for (int j = 1; j < 21; j++) {
        for (int i = 1; i <= n; i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
            qmin[i][j] = min(qmin[i][j - 1], qmin[par[i][j - 1]][j - 1]);
            qmax[i][j] = max(qmax[i][j - 1], qmax[par[i][j - 1]][j - 1]);
        }
    }
}
pair<int, int> lca(int x, int y) {
    int rmin = INF;
    int rmax = -INF;
    if (d[x] > d[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--) {
        if (d[y] - d[x] >= (1 << i)) {
            rmin = min(rmin, qmin[y][i]);
            rmax = max(rmax, qmax[y][i]);
            y = par[y][i];
        }
    }
    if (x == y)
        return{ rmin,rmax };
    for (int i = 20; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            rmin = min(rmin, min(qmin[x][i], qmin[y][i]));
            rmax = max(rmax, max(qmax[x][i], qmax[y][i]));
            x = par[x][i];
            y = par[y][i];
        }
    }
    rmin = min(rmin, min(qmin[x][0], qmin[y][0]));
    rmax = max(rmax, max(qmax[x][0], qmax[y][0]));
    return{ rmin,rmax };
}
int main() {
    scanf("%d", &n);
    vt.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        vt[a].emplace_back(b, c);
        vt[b].emplace_back(a, c);
    }
    dfs(1, 0);
    f();
    scanf("%d", &k);
    while (k--) {
        int a, b;
        scanf("%d%d", &a, &b);    
        pair<int, int> r = lca(a, b);
        printf("%d %d\n", r.first, r.second);
    }
    return 0;
}