#include #include #include #include #include #include #include using namespace std; typedef long long int ll; struct LowestCommonAncester{ int n,h; vector> g,par; vector dep; LowestCommonAncester(int n):n(n),g(n),dep(n){ h=1; while((1< (n,-1)); } void add_edge(int u,int v){ g[u].push_back(v); g[v].push_back(u); } void dfs(int v,int p,int d){ par[0][v]=p; dep[v]=d; for(auto u:g[v]){ if(u!=p)dfs(u,v,d+1); } } void build(int r){ dfs(r,-1,0); for(int i=0;i=0)par[i+1][j]=par[i][par[i][j]]; } } } int lca(int u,int v){ if(dep[u]>dep[v])swap(u,v); for(int i=0;i=0;i--){ if(par[i][u]!=par[i][v])u=par[i][u],v=par[i][v]; } return par[0][u]; } int distance(int u,int v){ return dep[u]+dep[v]-dep[lca(u,v)]*2; } }; vector> g[200200]; int d[200200]; void dfs(int s,int p){ for(auto t:g[s]){ if(t.first==p)continue; d[t.first]=d[s]+t.second; dfs(t.first,s); } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; LowestCommonAncester LCA(n); for(int i=1;i> a >> b >> c; a--; b--; g[a].push_back({b,c}); g[b].push_back({a,c}); LCA.add_edge(a,b); } LCA.build(0); dfs(0,-1); int q; cin >> q; while(q--){ int s,t; cin >> s >> t; s--; t--; int l=LCA.lca(s,t); cout << d[s]+d[t]-2*d[l] << endl; } }