#include #define endl "\n" using std::cin; using std::cout; using std::vector; using ll=long long; const ll inf=(1ll<<60); struct tree{ int N; vector> dp; vector dist; tree(vector> edge){ N=edge.size(); dp.resize(N); dist.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 LCA(int X,int Y){ if(dist[X]=0;i--){ if(dp[X][i]!=dp[Y][i]){ X=dp[X][i]; Y=dp[Y][i]; } } return std::make_tuple(dp[X][0],X,Y); } }; struct Segment_tree{ int N; vector node; Segment_tree(int n):N(n){ { int X=1; while(X> &edge,vector> &weight,tree &tr,Segment_tree &seg,vector>> &memo,vector &min){ vector data; std::map cnt,match; for(int i=0;itr.dist[now]) data.push_back(weight[now][i]); cnt[weight[now][i]]++; match[next]=weight[now][i]; } sort(data.begin(),data.end()); for(int i=0;itr.dist[now]){ ll Z=data[0]; if(Z==weight[now][i]){ if(data.size()==1) Z=inf; else Z=data[1]; } seg.update(tr.dist[now],Z); dfs(N,next,edge,weight,tr,seg,memo,min); seg.update(tr.dist[now],inf); } } for(auto p:memo[now]){ int X,Y,Z; std::tie(X,Y,Z)=p; if(X>=0){ if(data.empty()) data.push_back(inf); min[X]=std::min({min[X],seg.query(Y+1,Z,0,0,-1),data[0]}); } else{ X=-X-1; cnt[match[Y]]--; if(cnt[match[Y]]==0) cnt.erase(match[Y]); if(Z>=0){ cnt[match[Z]]--; if(cnt[match[Z]]==0) cnt.erase(match[Z]); } if(!cnt.empty()) min[X]=std::min(min[X],(ll)(*begin(cnt)).first); cnt[match[Y]]++; if(Z>=0) cnt[match[Z]]++; } } } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); const ll MAX=1e5; const ll INF=1e9; int N; cin>>N; assert(1<=N&&N<=MAX); vector> edge(N),weight(N); for(int i=1;i>X>>Y>>Z; assert(1<=X&&X<=N&&1<=Y&&Y<=N&&1<=Z&&Z<=INF); edge[X-1].push_back(Y-1); edge[Y-1].push_back(X-1); weight[X-1].push_back(Z); weight[Y-1].push_back(Z); } tree tr(edge); int Q; cin>>Q; assert(1<=Q&&Q<=MAX); vector>> memo(N); vector min(Q,inf),sum(Q),dist(N,-1); dist[0]=0; std::queue que; que.push(0); while(!que.empty()){ int now=que.front(); que.pop(); for(int i=0;i>X>>Y; assert(1<=X&&X<=N&&1<=Y&&Y<=N&&X!=Y); X--,Y--; int Z,x,y; std::tie(Z,x,y)=tr.LCA(X,Y); if(X!=Z) memo[X].push_back(std::make_tuple(i,tr.dist[Z],tr.dist[X])); if(Y!=Z) memo[Y].push_back(std::make_tuple(i,tr.dist[Z],tr.dist[Y])); memo[Z].push_back(std::make_tuple(-i-1,x,y)); sum[i]=dist[X]+dist[Y]-2*dist[Z]; } Segment_tree seg(N); dfs(N,0,edge,weight,tr,seg,memo,min); for(int i=0;i