3176_도로네트워크

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define inf 10000000
 
int n, a, b, c, k, d, e;
int mx = 0, mn = inf;
int par[100001][21], maxx[100001][21], minn[100001][21];
int visit[100001], dep[100001];
vector<vector<pair<int, int>>> adj;
 
void dfs(int cur, int d) {
    visit[cur] = 1;
    dep[cur] = d;
 
    for (auto i : adj[cur]) {
        if (!visit[i.first]) {
            par[i.first][0] = cur;
            maxx[i.first][0] = i.second;
            minn[i.first][0] = i.second;
            dfs(i.first, d + 1);
        }
    }
}
 
void func(int n) {
    for (int j = 1; j < 21; j++) {
        for (int i = 1; i <= n; i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
            if (maxx[par[i][j - 1]][j - 1]) {
                maxx[i][j] = max(maxx[i][j - 1], maxx[par[i][j - 1]][j - 1]);
            }
            if (minn[par[i][j - 1]][j - 1]) {
                minn[i][j] = min(minn[i][j - 1], minn[par[i][j - 1]][j - 1]);
            }
        }
    }
}
 
 
int largest(int a, int b, int c) {
    int ret = a;
    ret > b ? ret : ret = b;
    ret > c ? ret : ret = c;
    return ret;
}
 
int smallest(int a, int b, int c) {
    int ret = a;
    ret < b ? ret : ret = b;
    ret < c ? ret : ret = c;
    return ret;
}
 
void lca(int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
 
    for (int i = 20; i >= 0; i--) {
        if (dep[y] - dep[x] >= (1 << i)) {
            mx = max(mx, maxx[y][i]);
            mn = min(mn, minn[y][i]);
            y = par[y][i];
        }
    }
 
    if (x == y) {
        return;
    }
 
    for (int i = 20; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            mx = largest(mx, maxx[x][i], maxx[y][i]);
            mn = smallest(mn, minn[y][i], minn[x][i]);
            x = par[x][i];
            y = par[y][i];
        }
    }
 
    mx = largest(mx, maxx[x][0], maxx[y][0]);
    mn = smallest(mn, minn[y][0], minn[x][0]);
 
}
 
int main() {
    scanf("%d", &n);
    adj.resize(n + 1);
 
    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 });
    }
 
    dfs(1, 0);
    func(n);
 
    scanf("%d", &k);
    while (k--) {
        scanf("%d %d", &d, &e);
        mx = 0; mn = inf;
        lca(d, e);
 
        printf("%d %d\n", mn, mx);
    }
 
}
 

딱 1년정도 전쯤에 풀었던 lca 문제이다.

이땐 이것도 길다고 찡찡댔는데 지금은..