#include #include using namespace std; using namespace atcoder; using ll = long long; constexpr ll mod = 1e9 + 7; constexpr ll INF = 1LL << 60; #define REP(i, init, n) for(int i = (int)(init); i < (int)(n); i++) #define vi vector #define vl vector #define vvi vector> #define vvl vector> #define pint pair #define plong pair int N, Q, digit; vector> G; vvi Parents; vl dist, depth; template void vv_output(vector> A, bool blank = true) { for(auto row: A) { for(auto a: row) { if(blank) cout << a << ' '; else cout << a; } cout << endl; } } void dfs(int parent) { for(auto child: G[parent]) { if(child.first == 0 || Parents[child.first][0] >= 0) continue; Parents[child.first][0] = parent; dist[child.first] = dist[parent] + child.second; depth[child.first] = depth[parent] + 1; dfs(child.first); } } int lcs(int u, int v) { if(depth[u] > depth[v]) swap(u, v); for(int k = 0; k < digit; k++) { if((depth[v] - depth[u]) >> k & 1) { v = Parents[v][k]; } } if(u == v) return u; for(int k = digit - 1; k >= 0; k--) { if(Parents[u][k] != Parents[v][k]) { u = Parents[u][k]; v = Parents[v][k]; } } return Parents[u][0]; } void solve() { digit = 1; int n = N; while(n > 1) { n >>= 1; digit++; } Parents.resize(N, vi(digit, -1)); dist.resize(N, 0); depth.resize(N, 0); dfs(0); // vv_output(Parents); REP(i, 1, digit) { REP(j, 0, N) { if(Parents[j][i - 1] == -1) continue; Parents[j][i] = Parents[Parents[j][i - 1]][i - 1]; } } // vv_output(Parents); cin >> Q; REP(i, 0, Q) { int s, t; cin >> s >> t; s--; t--; int parent = lcs(s, t); // cout << s << ' ' << t << ' ' << parent << endl; cout << dist[s] + dist[t] - 2 * dist[parent] << endl; } } int main() { cin >> N; G.resize(N); REP(i, 0, N - 1) { int a, b, c; cin >> a >> b >> c; a--; b--; G[a].push_back({b, c}); G[b].push_back({a, c}); } solve(); }