#include #include #include using namespace std; struct union_find { vector par; vector rank; union_find(int n) : par(n) , rank(n) { for(int i = 0;i < n;i++) par[i] = i; } int root(int i) { return par[i] == i ? i : par[i] = root(par[i]); } /* unite x, y return parent */ int unite(int x,int y) { x = root(x); y = root(y); if(x == y) return -1; if(rank[x] < rank[y]) { par[x] = y; return y; } else { par[y] = x; if(rank[x] == rank[y]) rank[x]++; return x; } } }; using i64 = long long; struct tarjans_offline_lca { using E = pair; vector> G; vector ance; union_find uf; vector weight; vector> query; vector>> q; vector ans; tarjans_offline_lca(int n): G(n), ance(n), uf(n), weight(n), q(n) {} void add_edge(int a, int b, i64 w) { G[a].push_back({ b, w }); G[b].push_back({ a, w }); } void add_query(int a, int b) { int i = query.size(); query.push_back({ a, b }); q[a].push_back({ b, i }); q[b].push_back({ a, i }); } void dfs(int v, int f, i64 W) { ance[v] = v; weight[v] = W; for(auto e: G[v]) { int u = e.first; i64 w = e.second; if(f == u) continue; dfs(u, v, w + W); uf.unite(u, v); ance[uf.root(v)] = v; } for(auto e: q[v]) { int u = e.first; int i = e.second; if(ans[i] == -1) ans[i] = -2; else if(ans[i] == -2) ans[i] = ance[uf.root(u)]; } } void offline_lca(int root) { ans.assign(query.size(), -1); dfs(root, -1, 0); } }; #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; i64 N; fin >> N; tarjans_offline_lca 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); } i64 Q; fin >> Q; for(i64 q = 0; q < Q; q++) { i64 x, y, z; fin >> x >> y >> z; eul.add_query(x, y); eul.add_query(y, z); eul.add_query(x, z); } eul.offline_lca(0); auto dist = [&](i64 i) -> i64 { int a = eul.query[i].first; int b = eul.query[i].second; int c = eul.ans[i]; return eul.weight[a] + eul.weight[b] - 2 * eul.weight[c]; }; for(i64 q = 0; q < Q; q++) { fout << (dist(q * 3) + dist(q * 3 + 1) + dist(q * 3 + 2)) / 2 << "\n"; } }