DISTQUERY SPOJ, Euler tour + segtree

#include <bits/stdc++.h>
using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
#define NeedForSpeed                  \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define int long long
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vpi;
typedef pair<int, int> pi;
#define f first
#define s second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define set_bits __builtin_popcountll
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define endl "\n"
#define M_PI 3.14159265358979323846264338327950288
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const long long INF = 2e18;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int N = 1e5 + 5;
const int L = 20;
#ifndef ONLINE_JUDGE
#include "heWhoCooks.cpp"
#else
#define debug(...)
#define debugArr(...)
#define __START__
#define __END__
#endif
struct segtree
{
    typedef pair<int, int> T;
    T def = {INF, -INF}, t[2 * N];
    // min and max pair
    T f(T a, T b) { return {min(a.f, b.f), max(a.s, b.s)}; }
    void build(const vector<int> &v)
    {
        int n = v.size();
        for (int i = 0; i < n; ++i)
        {
            t[i + N] = {v[i], v[i]};
        }
        for (int i = N - 1; i > 0; --i)
        {
            t[i] = f(t[2 * i], t[2 * i + 1]);
        }
    }
    void modify(int p, T v)
    {
        for (t[p += N] = v; p /= 2;)
        {
            t[p] = f(t[2 * p], t[2 * p + 1]);
        }
    }
    T query(int l, int r)
    {
        T resl = def, resr = def;
        for (l += N, r += N; l < r; l /= 2, r /= 2)
        {
            if (l & 1)
            {
                resl = f(resl, t[l++]);
            }
            if (r & 1)
            {
                resr = f(t[--r], resr);
            }
        }
        return f(resl, resr);
    }
};
vpi adj[N];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= (n - 1); i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    vi in(n + 1), out(n + 1), euler, cost;
    function<void(int, int)> dfs = [&](int u, int p)
    {
        in[u] = sz(euler);
        for (auto &[v, w] : adj[u])
        {
            if (v == p)
            {
                continue;
            }
            cost.pb(w);
            euler.pb(v);
            dfs(v, u);
            cost.pb(w);
            euler.pb(u);
        }
        out[u] = sz(euler);
    };
    dfs(1, 0);
    debug(euler);
    debug(cost);
    segtree st;
    st.build(cost);
    int q;
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        int l = min(in[u], in[v]), r = max(in[u], in[v]);
        auto ans = st.query(l, r);
        cout << ans.f << " " << ans.s << endl;
    }
}

signed main()
{
    __START__;
    NeedForSpeed;
    int t = 1;
    while (t--)
    {
        solve();
    }
    __END__;
    return 0;
}