[LCA] BOJ 3176 도로 네트워크

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

3176번: 도로 네트워크

[필요한 개념 : LCA (이분 탐색)]

최소 공통 조상 (LCA, Lowest Common Ancestor)

[먼저 풀면 좋은 문제]

[LCA] BOJ 1761 정점들의 거리

 

문제에서 N개의 도시를 N - 1개의 도로로 모두 연결한다 했으므로, 각 도시의 연결 구조는 트리 구조임을 알 수 있다.

 

우선 선형 시간에 LCA를 구해보며 이 문제의 답을 구해보자.

트리 구조에서 두 정점 간 경로는 유일하므로, 그 경로에 포함되는 간선들의 집합 또한 유일하다.

즉, x = Parent[x] 연산을 해나가며 그때그때 최솟값과 최댓값을 갱신해주면 쉽게 답을 구할 수 있다.

 

하지만, 선형 시간에 LCA를 구한다면 제한 시간 안에 답을 구할 수 없다.

N이 10만에, LCA를 찾는 쿼리 또한 10만 번이기 때문에 우리는 LCA를 이분 탐색으로 구해야 한다.

이제는 조상 노드로 거슬러 올라가는 단위가 2^k번째 꼴이기 때문에, 선형 시간에 LCA를 구할 때보다 최대, 최소 간선을 구하는 것이 복잡해진다.

이분 탐색으로 LCA를 구할 때 사용한 점화식은 아래와 같다.

Parent[x][k] = Parent[Parent[x][k - 1]][k - 1]

이 식을 그대로 응용해, 다음과 같은 접근으로 최대, 최소 간선을 구한다.

Parent_maxdist[x][k] =

max(Parent_mindist[x][k], Parent_maxdist[Parent_maxdist[x][k - 1]][k - 1])

(정점 x의 2^k번째 조상까지의 간선들 중 최대 가중치 간선, 코드의 parent_dist[0])

Parent_mindist[x][k] =

min(Parent_mindist[x][k], Parent_mindist[Parent_mindist[x][k - 1]][k - 1])

(정점 x의 2^k번째 조상까지의 간선들 중 최소 가중치 간선, 코드의 parent_dist[1])

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
#define INF 99999999
 
using namespace std;
typedef pair<int, int> p;
 
vector<p> adj[100001];
int n, k, parent[100001][20], level[100001];
int parent_dist[100001][20][2];
int maxlevel;
 
p get_answer(int a, int b) {
    bool flag = false;
    int ret_max = 0, ret_min = INF;
    //레벨이 더 높은 노드를 a로 둔다.
    if (level[a] < level[b]) swap(a, b);
 
    //두 노드의 레벨이 다르다면 맞춰줌
    if (level[a] != level[b]) {
        for (int i = maxlevel; i >= 0; i--) {
            if (level[parent[a][i]] >= level[b]) {
                ret_max = max(ret_max, parent_dist[a][i][0]);
                ret_min = min(ret_min, parent_dist[a][i][1]);
                a = parent[a][i];
            }
        }
    }
 
    //최소 공통 조상을 찾는다.
    if (a != b) {
        for (int i = maxlevel; i >= 0; i--) {
            if (parent[a][i] != parent[b][i]) {
                ret_max = max({ ret_max, parent_dist[a][i][0], parent_dist[b][i][0] });
                ret_min = min({ ret_min, parent_dist[a][i][1], parent_dist[b][i][1] });
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        ret_max = max({ ret_max, parent_dist[a][0][0], parent_dist[b][0][0] });
        ret_min = min({ ret_min, parent_dist[a][0][1], parent_dist[b][0][1] });
    }
 
    return { ret_min, ret_max };
}
 
void set_tree(int node, int pnode, int lv, int pdist) {
    parent[node][0] = pnode;
    parent_dist[node][0][0] = pdist;    //최댓값
    level[node] = lv;
 
    if (node == 1) parent_dist[node][0][1] = INF;
    else parent_dist[node][0][1] = pdist;    //최솟값
 
    for (int i = 1; i <= maxlevel; i++) {
        parent[node][i] = parent[parent[node][i - 1]][i - 1];
 
        parent_dist[node][i][0] = max(parent_dist[node][i - 1][0], parent_dist[parent[node][i - 1]][i - 1][0]);
 
        parent_dist[node][i][1] = min(parent_dist[node][i - 1][1], parent_dist[parent[node][i - 1]][i - 1][1]);
    }
 
    for (int i = 0; i < adj[node].size(); i++) {
        int childnode = adj[node][i].first;
        if (childnode == pnode) continue;
        set_tree(childnode, node, lv + 1, adj[node][i].second);
    }
}
 
void init() {
    int u, v, w;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    maxlevel = (int)floor(log2(100001));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= maxlevel; j++) {
            parent_dist[i][j][0] = 0;
            parent_dist[i][j][1] = INF;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    set_tree(1, 1, 1, 0);
 
    cin >> k;
    int f, s;
    for (int i = 0; i < k; i++) {
        cin >> f >> s;
        p result = get_answer(f, s);
        printf("%d %d\n", result.first, result.second);
    }
 
    return 0;
}