#include #include #include #include #include #include #include #include #include #include #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=1e9+7; template void chmin(T &a,const T &b){if(a>b) a=b;} template void chmax(T &a,const T &b){if(a #include //SegmentTree seg(N,[](int a,int b){return min(a,b);},INT_MAX); template< typename T> class SegmentTree{ public: using F = function; int n; vector tree; F operation; T def; SegmentTree(int size,F _operation,T _def):operation(_operation),def(_def){ n=1; while(n v){ int vSize=v.size(); n=1; while(n=0;i--) tree[i]=operation(tree[2*i+1],tree[2*i+2]); } void update(int index,T value){ index+=n-1; tree[index]=value; while(index>0){ index=(index-1)/2; tree[index]=operation(tree[2*index+1],tree[2*index+2]); } } T query(int a,int b,int k=0,int l=0,int r=-1){//[a,b),getMin(a,b,0,0,-1) if(r<0) r=n; if(r<=a||b<=l) return def; else if(a<=l&&r<=b) return tree[k]; else{ T lval=query(a,b,2*k+1,l,(l+r)/2); T rval=query(a,b,2*k+2,(l+r)/2,r); return operation(lval,rval); } } int find(int x,int k=0,int l=0,int r=-1){// a[0]+...+a[i]>=x (i:minimal) if(r<0) r=n; if(r-l==1) return k-(n-1); if(tree[2*k+1]>=x) return find(x,2*k+1,l,(l+r)/2); else return find(x-tree[2*k+1],2*k+2,(l+r)/2,r); } int find_left(int a,int b,T x,int k=0,int l=0,int r=-1){// max(a[a],...,a[i])>=x (i:minimal) if(r<0) r=n; if(tree[k]=0) return vl; return find_left(a,b,x,2*k+2,(l+r)/2,r); } }; struct LowestCommonAncestor{ #define MAX_LOG_V 25 vector> g; int root; vector parent[MAX_LOG_V]; vector depth; LowestCommonAncestor(){} LowestCommonAncestor(int V,int root_):g(V),depth(V){ root=root_; for(int i=0;idepth[v]) swap(u,v); for(int k=0;k>k&1){ v=parent[k][v]; } } if(u==v) return u; for(int k=MAX_LOG_V-1;k>=0;k--){ if(parent[k][u]!=parent[k][v]){ u=parent[k][u]; v=parent[k][v]; } } return parent[0][u]; } }; int N; vector>> g; int Q; vector X,Y; vector L; LowestCommonAncestor lca; vector dist; vector>> miedge; const ll INF=1e15; SegmentTree seg; vector> qxy,qlca; vector trans; int segpos=0; vector ans; void predfs(int now,int par,ll d){ dist[now]=d; for(auto e:g[now]){ int nex=e.first; ll c=e.second; for(int i=0;i<3;i++){ if(miedge[now][i].first>c){ for(int j=2;j-1>=i;j--) miedge[now][j]=miedge[now][j-1]; miedge[now][i]=mkp(c,nex); break; } } if(nex==par) continue; predfs(nex,now,d+c); } } void eulertour(int now,int par){ for(auto tar:qxy[now]){// x (x != lca(x,y)) if(miedge[now][0].second==par) chmin(ans[tar],miedge[now][1].first); else chmin(ans[tar],miedge[now][0].first); if(par==L[tar]) continue; int lef=trans[L[tar]]; ll res=seg.query(lef+1,segpos); chmin(ans[tar],res); } for(auto tar:qlca[now]){// lca for(int i=0;i<3;i++){ int chnode=miedge[now][i].second; int lc=lca.query(X[tar],chnode); if(lc!=par&&lc!=L[tar]) continue; lc=lca.query(Y[tar],chnode); if(lc!=par&&lc!=L[tar]) continue; chmin(ans[tar],miedge[now][i].first); } } for(auto e:g[now]){ int nex=e.first; ll c=e.second; if(nex==par) continue; ll nc=c; for(int i=0;i<3;i++){ if(miedge[now][i].second==par) continue; if(miedge[now][i].second==nex) continue; nc=miedge[now][i].first; break; } seg.update(segpos,nc); trans[now]=segpos++; eulertour(nex,now); segpos--; trans[now]=-1; seg.update(segpos,INF); } } int main(){ cin.tie(0); ios::sync_with_stdio(false); cin>>N; g.resize(N); lca.initialize(N,0); dist.resize(N,0); rep(i,N-1){ int a,b,c; cin>>a>>b>>c; a--;b--; g[a].push_back(mkp(b,c)); g[b].push_back(mkp(a,c)); lca.add_edge(a,b); } lca.build(N); cin>>Q; X.resize(Q); Y.resize(Q); L.resize(Q); rep(i,Q) cin>>X[i]>>Y[i]; rep(i,Q){ X[i]--;Y[i]--; L[i]=lca.query(X[i],Y[i]); } miedge.resize(N); rep(i,N){ miedge[i].resize(3); rep(j,3) miedge[i][j]=mkp(INF,-1); } seg.embody(N,[](ll a,ll b){return min(a,b);},INF); qxy.resize(N); qlca.resize(N); rep(i,N){ if(X[i]!=L[i]) qxy[X[i]].push_back(i); if(Y[i]!=L[i]) qxy[Y[i]].push_back(i); qlca[L[i]].push_back(i); } trans.resize(N,-1); ans.resize(Q,INF); predfs(0,-1,0); eulertour(0,-1); rep(i,Q){ if(ans[i]==INF) ans[i]=-1; else ans[i]=2*ans[i]+dist[X[i]]+dist[Y[i]]-2*dist[L[i]]; } rep(i,Q) cout<