#include using namespace std; #define ll long long #define all(x) x.begin(),x.end() #define rep(i,a,b) for(int i=a;i<=b;i++) #define rep_r(i,a,b) for(int i=a;i>=b;i--) #define each(a,x) for (auto& x : a) using pi = pair; using pl = pair; using vi = vector; using vl = vector; #define sz(x) int(x.size()) #define so(x) sort(all(x)) #define so_r(x) sort(all(x),greater()) #define lb lower_bound #define ub upper_bound const char nl = '\n'; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int bit_cnt(int x){ return __builtin_popcount(x); } ll bex(ll a, ll b, ll mod = 1e9 + 7){ll res = 1LL; while(b){ if (b&1) res = res * a % mod; a = a * a % mod; b >>= 1;} return res;} template bool chmax(t&a,u b){if(a bool chmin(t&a,u b){if(b B with cost C // Q queries: find cost from s[j] to t[j] in each query // this probably use RMQ // dist[i,j] = cost[i] + cost[j] - 2 * cost[fa[i,j]] vector> g[N]; int cost[N]; // https://wiki.vnoi.info/algo/data-structures/lca-binlift.md int h[N]; int up[N][20]; void dfs(int u, int fa){ each(g[u],ed){ int v = ed.first, w = ed.second; if (v == fa) continue; h[v] = h[u] + 1; up[v][0] = u; for (int j = 1; j < 20; j++){ up[v][j] = up[up[v][j-1]][j-1]; } cost[v] = cost[u] + w; dfs(v,u); } } int lca(int u, int v){ if (h[u] != h[v]){ if (h[u] < h[v]) swap(u,v); int k = h[u] - h[v]; for (int j = 0; (1 << j) <= k; j++){ if (k>>j&1) u = up[u][j]; } } if (u == v) return u; int k = log2(h[u]); for (int j = k; j >= 0; j--){ if (up[u][j] != up[v][j]) { u = up[u][j]; v = up[v][j]; } } return up[u][0]; } int calc(int u, int v){ int fa = lca(u,v); return cost[u] + cost[v] - 2 * cost[fa]; } void solve(){ int n; cin >> n; rep(_,1,n-1){ int a,b,c; cin >> a >> b >> c; g[a].push_back({b,c}); g[b].push_back({a,c}); } dfs(1,1); int q; cin >> q; while (q--){ int s,t; cin >> s >> t; cout << calc(s,t) << nl; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; // cin >> t; while (t--){ solve(); } }