LUBENICA (vnoj) - LCA (Độ dài con đường ngắn nhất, dài nhất giữa 2 đỉnh)

// https://oj.vnoi.info/problem/lubenica
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pi32 = pair<int, int>;

const int N = 1e5 + 5;
const int M = log2(N) + 1;
const int INF = 1e9 + 7;

struct Data {
    int par, minc = INF, maxc = -INF;
};

int n, l;
vector<pi32> graph[N];

int height[N];
Data up[N][M];

void DFS(int u, int p) {
    up[u][0].par = p;

    for (auto &e : graph[u]) {
        int v = e.first;
        int uv = e.second;

        if (v == p) continue;

        height[v] = height[u] + 1;
        up[v][0].maxc = up[v][0].minc = uv;
        DFS(v, u);
    }
}

void buildLCA() {
    l = log2(n);

    DFS(1, 1);
    for (int i = 1; i <= l; i++) {
        for (int u = 1; u <= n; u++) {
            up[u][i].par = up[up[u][i - 1].par][i - 1].par;
            up[u][i].maxc = max(up[u][i - 1].maxc, up[up[u][i - 1].par][i - 1].maxc);
            up[u][i].minc = min(up[u][i - 1].minc, up[up[u][i - 1].par][i - 1].minc);
        }
    }
}

void solve(int u, int v) {
    Data res;
    if (height[u] < height[v]) swap(u, v);
    for (int i = l; i >= 0; i--) {
        if(height[u] - (1 << i) >= height[v]) {
            res.maxc = max(res.maxc, up[u][i].maxc);
            res.minc = min(res.minc, up[u][i].minc);
            u = up[u][i].par;
        }
    }

    if (u == v) {
        cout << res.minc << ' ' << res.maxc << '\n';
        return;
    }

    for (int i = l; i >= 0; --i) {
        if (up[u][i].par != up[v][i].par) {
            res.maxc = max({res.maxc, up[u][i].maxc, up[v][i].maxc});
            res.minc = min({res.minc, up[u][i].minc, up[v][i].minc});
            u = up[u][i].par; v = up[v][i].par;
        }
    }

    res.maxc = max({res.maxc, up[u][0].maxc, up[v][0].maxc});
    res.minc = min({res.minc, up[u][0].minc, up[v][0].minc});

    cout << res.minc << ' ' << res.maxc << '\n';
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#else
    freopen("LUBENICA.inp", "r", stdin);
    freopen("LUBENICA.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n - 1; ++i) {
        int u, v, w; cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    buildLCA();

    int nTest; cin >> nTest;
    while (nTest--) {
        int u, v; cin >> u >> v;
        solve(u, v);
    }

    return 0;
}