#include using namespace std; using i64 = long long; struct heavy_light_decomposition { int N; std::vector>> G; std::vector in; std::vector sz; std::vector next; std::vector par; std::vector weight; heavy_light_decomposition(int n) : N(n), G(n), in(n), sz(n, 1), next(n, -1), par(n, -1), weight(n) {} void add_edge(int u, int v, i64 w) { G[u].push_back({ v, w }); G[v].push_back({ u, w }); } void build(int r) { std::vector st(N); std::vector seq(N); std::vector idx(N, -1); int si = 0; int qi = 0; st[si++] = r; while(si > 0) { int v = st[--si]; st[si] = 0; seq[qi++] = v; for(int i = 0; i < G[v].size(); i++) { int t = G[v][i].first; if(par[v] == t) continue; par[t] = v; idx[t] = i; st[si++] = t; weight[t] = weight[v] + G[v][i].second; } } for(int i = N; i --> 0;) { int v = seq[i]; int p = par[v]; if(p >= 0) { sz[p] += sz[v]; if(st[p] < sz[v]) { st[p] = sz[v]; std::swap(G[p][0], G[p][idx[v]]); } } } si = 0; qi = 0; st[si++] = r; while(si > 0) { int v = st[--si]; in[v] = qi++; for(int i = G[v].size(); i --> 0;) { int t = G[v][i].first; if(par[v] == t) continue; next[t] = (i == 0) ? next[v] : t; st[si++] = t; } } } i64 lca(i64 a, i64 b) const { while(true) { if(in[b] > in[a]) std::swap(a, b); if(next[b] == next[a]) return b; a = par[next[a]]; } } }; struct HeavyLightDecomposition { vector>> G; vector in; vector sz; vector next; vector par; vector weight; HeavyLightDecomposition(i64 n) : G(n), in(n), sz(n), next(n, -1), par(n), weight(n) {} void add_edge(i64 u, i64 v, i64 w) { G[u].push_back({ v, w }); G[v].push_back({ u, w }); } void dfs_sz(i64 v, i64 f, i64 W) { sz[v] = 1; weight[v] = W; for(i64 i = 0;i < G[v].size();i++) { i64 x = G[v][i].first; i64 w = G[v][i].second; if(x == f) continue; dfs_sz(x, v, W + w); par[x] = v; sz[v] += sz[x]; if(sz[G[v][0].first] < sz[G[v][i].first]) { swap(G[v][0], G[v][i]); } } } i64 dfs_eul(i64 v, i64 f, i64 t) { in[v] = t++; for(i64 i = 0;i < G[v].size();i++) { i64 x = G[v][i].first; if(x == f) continue; next[x] = (i == 0) ? next[v] : x; t = dfs_eul(x, v, t); } return t; } void build(i64 r) { dfs_sz(r, -1, 0); dfs_eul(r, -1, 0); } i64 lca(i64 a, i64 b) const { while(true) { if(in[b] > in[a]) swap(a, b); if(next[b] == next[a]) return b; a = par[next[a]]; } } }; #include namespace niu { char cur; struct FIN { static inline bool is_blank(char c) { return c <= ' '; } inline char next() { return cur = getc_unlocked(stdin); } inline char peek() { return cur; } inline void skip() { while(is_blank(next())){} } #define intin(inttype) \ FIN& operator>>(inttype& n) { \ bool sign = 0; \ n = 0; \ skip(); \ while(!is_blank(peek())) { \ if(peek() == '-') sign = 1; \ else n = (n << 1) + (n << 3) + (peek() & 0b1111); \ next(); \ } \ if(sign) n = -n; \ return *this; \ } intin(int) intin(long long) } fin; char tmp[128]; struct FOUT { static inline bool is_blank(char c) { return c <= ' '; } inline void push(char c) { putc_unlocked(c, stdout); } FOUT& operator<<(char c) { push(c); return *this; } FOUT& operator<<(const char* s) { while(*s) push(*s++); return *this; } #define intout(inttype) \ FOUT& operator<<(inttype n) { \ if(n) { \ char* p = tmp + 127; bool neg = 0; \ if(n < 0) neg = 1, n = -n; \ while(n) *--p = (n % 10) | 0b00110000, n /= 10; \ if(neg) *--p = '-'; \ return (*this) << p; \ } \ else { \ push('0'); \ return *this; \ } \ } intout(int) intout(long long) } fout; } #include int main() { using niu::fin; using niu::fout; using i64 = long long; i64 N; fin >> N; HeavyLightDecomposition eul(N); heavy_light_decomposition eul2(N); for(int i = 0;i < N - 1;i++) { i64 a, b, c; niu::fin >> a >> b >> c; eul.add_edge(a, b, c); eul2.add_edge(a, b, c); } eul.build(0); eul2.build(0); assert(eul.in == eul2.in); auto dist = [&](int a, int b) -> i64 { int c = eul.lca(a, b); return eul.weight[a] + eul.weight[b] - 2 * eul.weight[c]; }; i64 Q; fin >> Q; for(i64 q = 0; q < Q; q++) { i64 x, y, z; fin >> x >> y >> z; fout << (dist(x, y) + dist(y, z) + dist(z, x)) / 2 << "\n"; } }