[BOJ 3176] 도로 네트워크

문제 출처 : https://www.acmicpc.net/problem/3176

 

풀이 :

LCA 문제입니다.

LCA를 구하는 과정에 Max값과 Min값을 구하는 과정을 포함시켜

두 도시 사이의 경로 중 최소 최대값을 찾으시면 됩니다.

 

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> pi;
 
int n, k, a, b, c;
int depth[100001], low[100001][18], high[100001][18], anc[100001][18], visit[100001];
vector <pi>adj[100001];
 
void dfs(int idx) {
    visit[idx] = 1;
    for (pi next : adj[idx]) {
        if (visit[next.first])continue;
        int ni = next.first, p = next.second;
        depth[ni] = depth[idx] + 1;
        anc[ni][0] = idx;
        low[ni][0] = high[ni][0] = p;
        for (int i = 1, j = 1; j < depth[ni]; j *= 2, i++) {
            anc[ni][i] = anc[anc[ni][i - 1]][i - 1];
            low[ni][i] = min(low[ni][i-1], low[anc[ni][i - 1]][i - 1]);
            high[ni][i] = max(high[ni][i - 1], high[anc[ni][i - 1]][i - 1]);
        }
        dfs(ni);
    }
}
 
pi lca(int l, int r) {
    int Max = 0, Min = 1e9;
    if (depth[l] > depth[r])swap(l, r);
    for (int i = 17; i >= 0; i--)if (depth[r] - depth[l] >= (1 << i)) {
        Max = max(Max, high[r][i]);
        Min = min(Min, low[r][i]);
        r = anc[r][i];
    }
    if (l == r)return { Min,Max };
    for (int i = 17; i >= 0; i--)if (anc[r][i] != anc[l][i]) {
        Max = max(max(Max, high[r][i]),high[l][i]);
        Min = min(min(Min, low[r][i]),low[l][i]);
        r = anc[r][i];
        l = anc[l][i];
    }
    Max = max(max(Max, high[r][0]), high[l][0]);
    Min = min(min(Min, low[r][0]), low[l][0]);
    return { Min,Max };
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    for (int i = 0; i <= n; i++)low[i][0] = 1e9;
    depth[1] = 1;
    dfs(1);
    scanf("%d", &k);
    while (k--) {
        scanf("%d %d", &a, &b);
        pi ret = lca(a, b);
        printf("%d %d\n", ret.first, ret.second);
    }
}