#include #include using namespace std; int N; vector >G[2<<17]; int dep[2<<17],pr[18][2<<17]; long cost[2<<17]; void dfs(int u,int p,int d,int c) { dep[u]=d; cost[u]=c; pr[0][u]=p; for(paire:G[u])if(e.first!=p) { dfs(e.first,u,d+1,c+e.second); } } int lca(int u,int v) { if(dep[u]>k&1) { u=pr[k][u]; } if(u==v)return u; for(int k=18;k--;)if(pr[k][u]!=pr[k][v]) { u=pr[k][u]; v=pr[k][v]; } return pr[0][u]; } main() { cin>>N; for(int i=1;i>a>>b>>c; a--,b--; G[a].push_back(make_pair(b,c)); G[b].push_back(make_pair(a,c)); } dfs(0,-1,0,0); for(int k=1;k<18;k++)for(int i=0;i>Q; for(;Q--;) { int u,v;cin>>u>>v; u--,v--; int w=lca(u,v); cout<