#define PROBLEM "https://yukicoder.me/problems/3407" #include using namespace std; #define call_from_test #ifndef call_from_test #include using namespace std; #endif //BEGIN CUT HERE struct LowestCommonAncestor{ int n,h; vector< vector > G,par; vector dep; LowestCommonAncestor(){} LowestCommonAncestor(int n):n(n),G(n),dep(n){ h=1; while((1<(n,-1)); } void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } void dfs(int v,int p,int d){ par[0][v]=p; dep[v]=d; for(int u:G[v]) if(u!=p) dfs(u,v,d+1); } void build(int r=0){ dfs(r,-1,0); for(int k=0;k+1dep[v]) swap(u,v); for(int k=0;k>k&1) v=par[k][v]; if(u==v) return u; for(int k=h-1;k>=0;k--) if(par[k][u]!=par[k][v]) u=par[k][u],v=par[k][v]; return par[0][u]; } int distance(int u,int v){ return dep[u]+dep[v]-dep[lca(u,v)]*2; } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #ifndef call_from_test #include using namespace std; #define call_from_test #include "lowestcommonancestor.cpp" #undef call_from_test #endif //BEGIN CUT HERE struct AuxiliaryTree : LowestCommonAncestor{ using super = LowestCommonAncestor; vector idx; vector> T; AuxiliaryTree(){} AuxiliaryTree(int n):super(n),idx(n),T(n){} void dfs(int v,int p,int &pos){ idx[v]=pos++; for(int u:G[v]) if(u!=p) dfs(u,v,pos); } void build(int r=0){ super::build(r); int pos=0; dfs(r,-1,pos); } void add_aux_edge(int u,int v){ T[u].emplace_back(v); T[v].emplace_back(u); } using super::lca, super::dep; void query(vector &vs){ assert(!vs.empty()); sort(vs.begin(),vs.end(), [&](int a,int b){return idx[a] st; st.emplace(vs[0]); for(int i=0;i+11){ int c=st.top();st.pop(); add_aux_edge(st.top(),c); } } void clear(const vector &ws){ for(int w:ws) T[w].clear(); } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n; cin>>n; AuxiliaryTree G(n); vector> ws(n); for(int i=1;i>u>>v>>w; G.add_edge(u,v); ws[u][v]=ws[v][u]=w; } G.build(); using ll = long long; vector dep(n,-1); queue que; dep[0]=0; que.emplace(0); while(!que.empty()){ int v=que.front();que.pop(); for(int u:G.G[v]){ if(~dep[u]) continue; dep[u]=dep[v]+ws[v][u]; que.emplace(u); } } int q; cin>>q; for(int i=0;i>k; vector vs(k); for(int j=0;j>vs[j]; G.query(vs); ll ans=0; for(int v:vs) for(int u:G.T[v]) ans+=max(dep[u]-dep[v],0LL); cout<