#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 FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #ifndef call_from_test #include using namespace std; #endif //BEGIN CUT HERE class EulerTourForVertex{ private: vector ls,rs; int pos; void dfs(int v,int p){ ls[v]=pos++; for(int u:G[v]) if(u!=p) dfs(u,v); rs[v]=pos; } public: vector< vector > G; EulerTourForVertex(){} EulerTourForVertex(int n):ls(n),rs(n),G(n){} void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } void build(int r=0){ pos=0; dfs(r,-1); } int idx(int v){return ls[v];} template void exec(int v,F f){ f(ls[v],rs[v]); } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #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 "eulertourforvertex.cpp" #include "lowestcommonancestor.cpp" #undef call_from_test #endif /** * @see https://smijake3.hatenablog.com/entry/2019/09/15/200200 */ //BEGIN CUT HERE struct AuxiliaryTree : EulerTourForVertex{ using super = EulerTourForVertex; LowestCommonAncestor lca; vector> T; AuxiliaryTree(){} AuxiliaryTree(int n):super(n),lca(n),T(n){} void build(int r=0){ super::build(r); lca.G=super::G; lca.build(r); } void add_aux_edge(int u,int v){ T[u].emplace_back(v); T[v].emplace_back(u); } using super::idx; void query(vector &vs){ assert(!vs.empty()); sort(vs.begin(),vs.end(), [&](int a,int b){return idx(a)> H; int k=vs.size(); stack 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(){ 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 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<