#include using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 2000000000000000000 vector>> e; struct Tree{ int G; vector L; vector number; vector Ts; vector>> E; vector mini; vector P; Tree(){ } Tree(vector>> EE){ E = EE; vector sz(E.size(),0); dfs(E,sz,0,-1); //cout< t(E[G].size(),0); for(int i=0;i>>> nE(E[G].size()); for(int i=0;i>()); } for(int i=0;i2){ Ts.resize(E[G].size()); for(int i=0;iE.size())f=false; } if((E.size()-sz[now])*2>E.size())f=false; if(f)G = now; } void dfs2(auto &E,int now,int p,int l,long long M){ mini[now] = M; P[now] = p; multiset> S; for(int i=0;isecond==to)it++; if(it!=S.end()){ t = it->first; } dfs2(E,to,now,l,min(M,t)); } } long long get(int u,int v){ if(u!=G&&v!=G&&L[u]==L[v]){ return Ts[L[u]].get(number[u],number[v]); } if(v==G)swap(u,v); long long ret = Inf; if(u!=G){ for(int i=0;i depth;//depth[i] 頂点iの深さ vector> parents;//parents[i][j] 頂点iから2^j個上の親 int max_j = 30; lca(int n,vector> &E){ depth.assign(E.size(),-1); parents.assign(E.size(),vector(max_j,-1)); stack s; s.push(n); depth[n] = 0; while(s.size()!=0){ int k = s.top(); s.pop(); for(int i=0;i=0;i--){ if(parents[u][i]!=parents[v][i]){ u = parents[u][i]; v = parents[v][i]; } } return parents[u][0]; } int get_distance(int u,int v){ return depth[u]+depth[v]-2*depth[query(u,v)]; } }; vector dis; void dfs(auto &E,int now,int p){ for(int i=0;i>N; e.resize(N,vector>()); vector> ee(N,vector()); for(int i=0;i>u>>v>>w; u--;v--; e[u].emplace_back(w,v); e[v].emplace_back(w,u); ee[u].push_back(v); ee[v].push_back(u); } for(int i=0;i>Q; for(int i=0;i