#include using namespace std; using i64 = long long; #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++) #define all(x) x.begin(),x.end() #define let auto const #pragma GCC target("avx2") struct eulartour_subtree { vector>> G; vector tour; vector L, R; vector depth; vector weight; eulartour_subtree(i64 n): G(n), L(n), R(n), depth(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(i64 v, i64 f, i64 d, i64 w) { tour.push_back(v); L[v] = tour.size() - 1; depth[v] = d; weight[v] = w; for(auto to: G[v]) { if(to.first == f) continue; dfs(to.first, v, d + 1, w + to.second); tour.push_back(v); } R[v] = tour.size() - 1; } i64 start_tour(i64 r) { dfs(r, -1, 0, 0); return tour.size(); } }; #include using namespace std; using i64 = long long; struct sparse_table { using Band = pair; Band ope(const Band& a, const Band b) { return min(a, b); } i64 N; vector A; vector log_t; vector> table; sparse_table(vector arr) : N(arr.size()), A(arr), log_t(arr.size() + 1) { for(int i = 2;i < N + 1;i++) { log_t[i] = log_t[i >> 1] + 1; } table.resize(N, vector(log_t[N] + 1)); for(int i = 0;i < N;i++) { table[i][0] = arr[i]; } for(int k = 1;(1 << k) <= N;k++) { for(int i = 0;i + (1 << k) <= N;i++) { table[i][k] = ope(table[i][k - 1], table[i + (1 << (k - 1))][k - 1]); } } } /* [s, t] */ Band query(i64 s, i64 t) { i64 k = log_t[t - s + 1]; return ope(table[s][k], table[t - (1 << k) + 1][k]); } }; #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; } int main() { using niu::fin; using niu::fout; i64 N; fin >> N; eulartour_subtree eul(N); for(int i = 0;i < N - 1;i++) { i64 a, b, c; fin >> a >> b >> c; eul.add_edge(a, b, c); } i64 sz = eul.start_tour(0); vector> arr(sz); for(i64 i = 0;i < sz;i++) { arr[i] = { eul.depth[eul.tour[i]], eul.tour[i] }; } sparse_table spa(arr); auto dist = [&](i64 a, i64 b) -> i64 { i64 c = spa.query(min(eul.L[a], eul.L[b]), max(eul.R[a], eul.R[b])).second; 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(x, z)) / 2 << "\n"; } }