#include using namespace std; using LL = long long int; #define incID(i, l, r) for(int i = (l) ; i < (r); ++i) #define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i) #define incII(i, l, r) for(int i = (l) ; i <= (r); ++i) #define decII(i, l, r) for(int i = (r) ; i >= (l); --i) #define inc(i, n) incID(i, 0, n) #define dec(i, n) decID(i, 0, n) #define inc1(i, n) incII(i, 1, n) #define dec1(i, n) decII(i, 1, n) #define inID(v, l, r) ((l) <= (v) && (v) < (r)) #define inII(v, l, r) ((l) <= (v) && (v) <= (r)) #define PB push_back #define EB emplace_back #define MP make_pair #define MT make_tuple #define FI first #define SE second #define FR front() #define BA back() #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() auto setmin = [](auto & a, auto b) { return (b < a ? a = b, true : false); }; auto setmax = [](auto & a, auto b) { return (b > a ? a = b, true : false); }; auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); }; auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); }; #define SI(v) static_cast(v.size()) #define RF(e, v) for(auto & e: v) #define until(e) while(! (e)) #define if_not(e) if(! (e)) #define ef else if #define UR assert(false) #define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__); void IN_() { }; template void IN_(T & a, U & ... b) { cin >> a; IN_(b ...); }; template void OUT(T && a ) { cout << a << endl; } template void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); } // ---- ---- #define bit(b, i) (((b) >> (i)) & 1) template T MV(T v) { return v; } template auto MV(T v, int a, U ... b) { return vector(a, MV(v, b ...)); } template class Forest { private: using Graph = vector>>; using Func = function; int n; Graph g; Func f; T id; bool ok = false; int B; vector d; vector> P; vector> U, D; vector vis; void dfs(int v, int p, T w) { if(vis[v]) { return; } vis[v] = true; if(v != p) { d[v] = d[p] + 1; } P[v][0] = p; U[v][0] = w; D[v][0] = w; RF(e, g[v]) { dfs(e.FI, v, e.SE); } } T fold_U(int a, int b) { assert(d[a] >= d[b]); T s = id; dec(k, B) { if(bit(d[a] - d[b], k) == 0) { continue; } s = f(s, U[a][k]); a = P[a][k]; } assert(a == b); return s; } T fold_D(int a, int b) { assert(d[b] >= d[a]); T s = id; dec(k, B) { if(bit(d[b] - d[a], k) == 0) { continue; } s = f(D[b][k], s); b = P[b][k]; } assert(b == a); return s; } public: Forest(Graph const & g, Func f, T id) : n(SI(g)), g(g), f(f), id(id) { } Forest(int n, Func f, T id) : n(n), g(n), f(f), id(id) { }; void add(int a, int b, T w) { ok = false; assert(inID(a, 0, n)); assert(inID(b, 0, n)); assert(a != b); g[a].EB(b, w); g[b].EB(a, w); } void init(vector const & r = { }) { ok = true; B = 1; until((1 << (B - 1)) >= n) { B++; } d = vector(n); P = MV(0, n, B); U = MV(id, n, B); D = MV(id, n, B); vis = vector(n, false); RF(e, r) { assert(inID(e, 0, n)); dfs(e, e, id); } inc(i, n) { dfs(i, i, id); } inc(k, B - 1) { inc(v, n) { int p = P[v][k]; P[v][k + 1] = P[p][k]; U[v][k + 1] = f(U[v][k], U[p][k]); D[v][k + 1] = f(D[p][k], D[v][k]); } } } int lca(int a, int b) { assert(ok); if(P[a][B - 1] != P[b][B - 1]) { return -1; } if_not(d[a] >= d[b]) { swap(a, b); } inc(k, B) { if(bit(d[a] - d[b], k)) { a = P[a][k]; } } if(a == b) { return a; } dec(k, B) { if(P[a][k] != P[b][k]) { a = P[a][k]; b = P[b][k]; } } a = P[a][0]; b = P[b][0]; assert(a == b); return a; } T fold(int a, int b) { int c = lca(a, b); if(c == -1) { return id; } return f(fold_U(a, c), fold_D(c, b)); } Graph const & get_g() { return g; } }; #define OP(s) [&](auto A, auto B) { return s; } // ---- int main() { IN(int, n); Forest t(n, OP(A + B), 0); inc(i, n - 1) { IN(int, a, b, c); a--; b--; t.add(a, b, c); } t.init(); IN(int, q); inc(qq, q) { IN(int, a, b); a--; b--; OUT(t.fold(a, b)); } }