#include using namespace std; #if __has_include() #include using namespace atcoder; templateistream &operator>>(istream &is,static_modint &a){long long b;is>>b;a=b;return is;} istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} #endif #ifdef LOCAL #include "debug.h" #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) #define esper(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<(0) ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } void SOLVE(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout<>testcase; for(int i=0;i>to; int root; vectorpar,pathtop,in,out,dep; vectorsub; private: void st_dfs(int x,int p){ par[x]=p; sub[x]=1; for(auto &i:to[x]){ if(i==p){ if(i==to[x].back())break; else swap(i,to[x].back()); } st_dfs(i,x); sub[x]+=sub[i]; if(sub[i]>sub[to[x][0]]){ swap(i,to[x][0]); } } } void hld_dfs(int x,int p,int &id){ in[x]=id++; for(auto i:to[x])if(i!=p){ dep[i]=dep[x]+1; pathtop[i]=(i==to[x][0]?pathtop[x]:i); hld_dfs(i,x,id); } out[x]=id; } public: HeavyLightDecomposition(int n,int root=0):n(n),to(n),sub(n),par(n),in(n),out(n),root(root),pathtop(n),dep(n),g(n){} void add_edge(int u,int v){ to[u].emplace_back(v); to[v].emplace_back(u); } void build(){ dep[root]=0; st_dfs(root,-1); pathtop[root]=root; int id=0; hld_dfs(root,-1,id); } inline int get(int x)const{return in[x];} int lca(int u,int v)const{ int pu=pathtop[u],pv=pathtop[v]; while(pathtop[u]!=pathtop[v]){ if(in[pu]>in[pv])u=par[pu],pu=pathtop[u]; else v=par[pv],pv=pathtop[v]; } return (in[u]>in[v]?v:u); } void subtree_query(int u ,const function &f){ f(in[u],out[u]); } void path_query(int u,int v,const function&f){ int pu=pathtop[u],pv=pathtop[v]; while(pathtop[u]!=pathtop[v]){ if(in[u]>in[v])f(in[pu],in[u]+1),u=par[pu],pu=pathtop[u]; else f(in[pv],in[v]+1),v=par[pv],pv=pathtop[v]; } if(in[u]>in[v])swap(u,v); f(in[u],in[v]+1); } void noncommutative_path_query(int u,int v,const function&f){ int l=lca(u,v); while(pathtop[u]!=pathtop[l]){ f(in[u]+1,in[pathtop[u]]); u=par[pathtop[u]]; } if(u!=l)f(in[u]+1,in[l]+1); f(in[l],in[l]+1); if(v==l)return; vector>query; while(true){ if(pathtop[l]==pathtop[v]){ query.emplace_back(in[l]+1,in[v]+1); break; } query.emplace_back(in[pathtop[v]],in[v]+1); v=par[pathtop[v]]; } reverse(all(query)); for(auto [i,j]:query)f(i,j); } vector>g; int auxiliary_tree(vectorv){ sort(all(v),[&](int x,int y){return in[x]st; rep(i,v.size()){ while(!st.empty()&&out[st.top()]<=in[v[i]])st.pop(); if(!st.empty()){ g[st.top()].push_back(v[i]); g[v[i]].push_back(st.top()); } st.push(v[i]); } while(st.size()>1)st.pop(); return st.top(); } }; void SOLVE(){ int n; cin>>n; HeavyLightDecomposition hld(n*2-1); vectorw(n-1); rep(i,n-1){ int u,v; cin>>u>>v>>w[i]; hld.add_edge(i+n,u); hld.add_edge(i+n,v); } hld.build(); fenwick_treeBIT(n*2-1); rep(i,n-1)BIT.add(hld.get(i+n),w[i]); int q; cin>>q; while(q--){ int k; cin>>k; vectorx(k); cin>>x; int root=hld.auxiliary_tree(x); ll ans=0; auto dfs=[&](auto self,int x,int p)->void { for(auto i:hld.g[x])if(i!=p){ hld.path_query(x,i,[&](int l,int r){ans+=BIT.sum(l,r);}); self(self,i,x); } }; dfs(dfs,root,-1); cout<