3176번: 도로 네트워크

https://www.acmicpc.net/problem/3176

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 100000, LGN = 16;
int n, k;
int dp[MAX_N + 1][LGN + 1], lv[MAX_N + 1];
bool ck[MAX_N + 1];
vector<pair<int, int> > adj[MAX_N + 1];
struct st {
    int mini, maxi;
    st() {}
    st(int _mini, int _maxi) :mini(_mini), maxi(_maxi) {}
    st operator+(st i) const {
        return st(min(mini, i.mini), max(maxi, i.maxi));
    }
}s[MAX_N + 1][LGN + 1];
void dfs(int h) {
    ck[h] = true;
    for (auto t : adj[h]) {
        if (ck[t.first]) continue;
        lv[t.first] = lv[h] + 1;
        dp[t.first][0] = h;
        s[t.first][0] = st(t.second, t.second);
        for (int i = 1; i <= LGN; i++) {
            s[t.first][i] = s[t.first][i - 1] + s[dp[t.first][i - 1]][i - 1];
            dp[t.first][i] = dp[dp[t.first][i - 1]][i - 1];
        }
        dfs(t.first);
    }
}
st res;
void lca(int x, int y) {
    res = st(1e6, 0);
    if (lv[x] < lv[y]) swap(x, y);
    for (int i = LGN; i >= 0; i--)
        if (1 << i <= lv[x] - lv[y])
            res = res + s[x][i], x = dp[x][i];
    if (x == y) return;
    for (int i = LGN; i >= 0; i--) {
        if (dp[x][i] != dp[y][i]) {
            res = res + s[x][i] + s[y][i];
            x = dp[x][i];
            y = dp[y][i];
        }
    }
    res = res + s[x][0] + s[y][0];
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({ b, c });
        adj[b].push_back({ a, c });
    }
    dfs(1);
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        lca(a, b);
        printf("%d %d\n", res.mini, res.maxi);
    }
    return 0;
}