#include #include #include using namespace std; vector> g[200000]; int p[200000][20]; long long cum[200000]; int dep[200000]; void dfs(int cur,int par,int d,int c) { cum[cur]=c; dep[cur]=d; p[cur][0]=par; for (auto e:g[cur]) if (e.first!=par) { dfs(e.first,cur,d+1,c+e.second); } } int lca(int a,int b) { if (a==b) return a; if (dep[a]0) { a=p[a][i]; } } return lca(a,b); } for (int i=19;i>=0;--i) { if (p[a][i]!=p[b][i]) { a=p[a][i]; b=p[b][i]; } } return p[a][0]; } int main() { int N,Q; cin>>N; for (int i=0;i>a>>b>>c; --a;--b; g[a].push_back({b,c}); g[b].push_back({a,c}); } dfs(0,-1,0,0); for (int i=1;i<20;++i) { for (int src=0;src>Q; for (int q=0;q>s>>t; --s;--t; w=lca(s,t); long long ans=cum[s]+cum[t]-2*cum[w]; cout<