#ifndef call_from_test #include using namespace std; #define call_from_test #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 #undef call_from_test #endif //BEGIN CUT HERE struct AuxiliaryTree : EulerTourForVertex{ using super = EulerTourForVertex; LowestCommonAncestor lca; AuxiliaryTree(){} AuxiliaryTree(int n):super(n),lca(n){} void build(int r=0){ super::build(r); lca.G=super::G; lca.build(r); } using super::idx; decltype(auto) 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]); H[vs[0]]; for(int i=0;i+11){ int c=st.top();st.pop(); H[st.top()].emplace_back(c); } return make_pair(st.top(),H); } }; //END CUT HERE #ifndef 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>k; vector vs(k); for(int j=0;j>vs[j]; auto H=G.query(vs).second; ll ans=0; for(int v:vs) for(int u:H[v]) ans+=dep[u]-dep[v]; cout<