#include #include #include using namespace std; #pragma GCC target("avx2") namespace niu { const int N_MAX = 1e5 + 1; int par[N_MAX]; int rank[N_MAX]; struct union_find { union_find(int 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; using E = pair; vector G[N_MAX]; int ance[N_MAX]; i64 weight[N_MAX]; int qi = 0; vector> q[N_MAX]; int ans[N_MAX * 3]; int query[N_MAX][3]; struct tarjans_offline_lca { union_find uf; tarjans_offline_lca(int n): uf(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) { q[a].push_back({ b, qi }); q[b].push_back({ a, qi }); qi++; } 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) { for(int i = 0; i < N_MAX * 3; i++) ans[i] = -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; using i64 = long long; i64 N; fin >> N; niu::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); niu::query[q][0] = x; niu::query[q][1] = y; niu::query[q][2] = z; } eul.offline_lca(0); auto dist = [&](i64 i, i64 j) -> i64 { int a = niu::query[i][j]; int b = niu::query[i][(j + 1) == 3 ? 0 : (j + 1)]; int c = niu::ans[i * 3 + j]; return niu::weight[a] + niu::weight[b] - 2 * niu::weight[c]; }; for(i64 q = 0; q < Q; q++) { fout << (dist(q, 0) + dist(q, 1) + dist(q, 2)) / 2 << "\n"; } }