#include using i64 = long long; struct heavy_light_decomposition { int N; std::vector>> G; std::vector in; std::vector out; std::vector sz; std::vector next; std::vector par; std::vector weight; heavy_light_decomposition(int n) : N(n), G(n), in(n), out(n, -1), 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]; out[v] = std::max(out[v], i + 1); if(p >= 0) { sz[p] += sz[v]; out[p] = std::max(out[p], out[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]]; } } }; #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; heavy_light_decomposition eul(N); for(int i = 0;i < N - 1;i++) { i64 a, b, c; niu::fin >> a >> b >> c; eul.add_edge(a, b, c); } eul.build(0); 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"; } }