BOJ 3176 도로 네트워크

1 개요[ | ]

BOJ 3176 도로 네트워크
2 C++[ | ]

#include <bits/stdc++.h>
using namespace std;

#define INF 1e9
vector<pair<int,int>> adj[100001];
int n, k, parent[100001][20], level[100001];
int parent_dist[100001][20][2];
const int MAXLEVEL = (int)log2(100001);

void show_answer(int a, int b) {
    int mx = 0;
    int mn = INF;
    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]) {
                mx = max(mx, parent_dist[a][i][0]);
                mn = min(mn, 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]) {
                mx = max({ mx, parent_dist[a][i][0], parent_dist[b][i][0] });
                mn = min({ mn, parent_dist[a][i][1], parent_dist[b][i][1] });
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        mx = max({ mx, parent_dist[a][0][0], parent_dist[b][0][0] });
        mn = min({ mn, parent_dist[a][0][1], parent_dist[b][0][1] });
    }
    cout << mn << ' ' << mx << '\n';
}
 
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);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int u, v, w;
    for (int i = 0; i < n - 1; i++) {
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    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;
        }
    }
    set_tree(1, 1, 1, 0);
    cin >> k;
    int f, s;
    for (int i=0; i<k; i++) {
        cin >> f >> s;
        show_answer(f, s);
    }
}