#include //using namespace std; #pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define rep(i,j,n) for(ll i=(ll)(j);i<(ll)(n);i++) #define REP(i,j,n) for(ll i=(ll)(j);i<=(ll)(n);i++) #define per(i,j,n) for(ll i=(ll)(j);(ll)(n)<=i;i--) #define ll long long #define ALL(a) (a).begin(),(a).end() #define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(ll)(key))) #define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(ll)(key))) #define pb emplace_back #define mp std::make_pair // #define endl "\n" //using std::endl; using std::cin; using std::cout; using std::vector; using std::string; using std::upper_bound; using std::lower_bound; using vi=vector; using vii=vector; using pii=std::pair; // constexpr ll MOD=1e9+7; //constexpr ll MOD=998244353; //constexpr ll MOD=10000000; //constexpr ll MOD=1e4; constexpr ll MAX=3e6; constexpr ll inf=(1ll<<60); template class prique :public std::priority_queue, std::greater> {}; template struct Segment_tree{ ll N; T mem; vector node; Segment_tree(vector &X,T m):mem(m){ ll sz=X.size(); N=1; while(N0){ X=(X-1)/2; node[X]=Compare(node[X*2+1],node[X*2+2]); } } T Query(ll a,ll b,ll now,ll l,ll r){ //[a,b),[l,r) if(r<0) r=N; if(r<=a||b<=l) return mem; if(a<=l&&r<=b) return node[now]; auto vl=Query(a,b,now*2+1,l,(l+r)/2),vr=Query(a,b,now*2+2,(l+r)/2,r); return Compare(vl,vr); } }; struct Tree{ int N; vector> dp; vector dist,par; vi dist2; Tree(vii edge){ N=edge.size(); dp.resize(N); dist.resize(N,-1); dist2.resize(N,-1); par.resize(N,-1); for(int i=0;i que; que.push(0); while(!que.empty()){ int now=que.front(); que.pop(); for(int i=0;i=0;i--){ if(dp[X][i]!=dp[Y][i]){ X=dp[X][i]; Y=dp[Y][i]; } } return dp[X][0]; } void make_dist2(vii edge,vii weight){ std::queue que; que.push(0); dist2[0]=0; while(!que.empty()){ int now=que.front(); que.pop(); for(int i=0;i0;x-=(x&-x)) ret+=bit[x]; return ret; } ll lower_bound(ll X){ if(sum(N)0){ if(memo+ret<=N&&sum+bit[memo+ret] 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } vi fac,finv,inv; void COMinit() { fac.resize(MAX); finv.resize(MAX); inv.resize(MAX); fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } ll COM(ll n,ll r){ if(n memo; rep(i,0,A.size()) memo[A[i]]=0; ll cnt=1; for(auto &p:memo) p.second=cnt++; rep(i,0,A.size()) A[i]=memo[A[i]]; } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); ll N; cin>>N; assert(N<=5000); vii edge(N),weight(N); rep(i,1,N){ ll X,Y,Z; cin>>X>>Y>>Z; edge[X-1].pb(Y-1); edge[Y-1].pb(X-1); weight[X-1].pb(Z); weight[Y-1].pb(Z); } Tree tr(edge); ll Q; cin>>Q; vii memo(N); vi pardist(N,inf); std::map to; rep(i,0,N){ rep(j,0,edge[i].size()){ int X=edge[i][j]; if(X==tr.par[i]) pardist[i]=weight[i][j]; else memo[i].pb(weight[i][j]); to[mp(i,X)]=weight[i][j]; } sort(ALL(memo[i])); } tr.make_dist2(edge,weight); rep(i,0,Q){ ll X,Y; cin>>X>>Y; X--,Y--; ll Z=tr.LCA(X,Y); ll ans=tr.dist2[Y]+tr.dist2[X]-tr.dist2[Z]*2; ll min=inf,me=-1; while(X!=Z){ ll P=inf; if(memo[X].size()>0){ if(memo[X][0]==me){ if(memo[X].size()>1) P=memo[X][1]; } else P=memo[X][0]; } min=std::min(min,P); if(tr.par[X]==Z) break; me=pardist[X]; X=tr.par[X]; } std::swap(X,Y); while(X!=Z){ ll P=inf; if(memo[X].size()>0){ if(memo[X][0]==me){ if(memo[X].size()>1) P=memo[X][1]; } else P=memo[X][0]; } min=std::min(min,P); if(tr.par[X]==Z) break; me=pardist[X]; X=tr.par[X]; } std::map map; rep(i,0,std::min(3,(int)memo[Z].size())) map[memo[Z][i]]++; map[pardist[Z]]++; if(to.count(mp(X,Z))&&map.count(to[mp(X,Z)])){ map[to[mp(X,Z)]]--; if(map[to[mp(X,Z)]]==0) map.erase(to[mp(X,Z)]); } std::swap(X,Y); if(to.count(mp(X,Z))&&map.count(to[mp(X,Z)])){ map[to[mp(X,Z)]]--; if(map[to[mp(X,Z)]]==0) map.erase(to[mp(X,Z)]); } if(!map.empty()) min=std::min(min,(*begin(map)).first); if(min==inf) ans=-1; else ans+=min*2; cout<