#include <string> #include <vector> #include <algorithm> #include <numeric> #include <set> #include <map> #include <queue> #include <iostream> #include <sstream> #include <cassert> #include <limits> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #define each(it,o) for(auto it= (o).begin(); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL #define inrep int t;cin>>t; while(t--) using namespace std; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii > vpii; typedef long long ll; typedef vector<ll> vll; typedef pair<ll,ll> pll; typedef vector<pll > vpll; typedef vector<string> vs; typedef long double ld; template<typename T> ostream& operator<< ( ostream &o,vector<T> v ) { if ( v.size() >0 ) o<<v[0]; for ( unsigned i=1; i<v.size(); i++ ) o<<" "<<v[i]; return o<<endl; } template<typename T,typename U> ostream& operator<< ( ostream &o,pair<T,U> v ) { return o<<"("<<v.first<<", "<<v.second<<")"; } template<typename T> istream& operator>> ( istream &in,vector<T> &v ) { for ( unsigned i=0; i<v.size(); i++ ) in>>v[i]; return in; } struct CentroidDecomp { const vector<vpii> &adj; const int n; vector<vi> dist; vector<vi> centers; vi order; vector<bool> removed; vi childs; int height; vector<bool> found; CentroidDecomp ( vector<vpii> &_adj ) :adj ( _adj ),n ( adj.size() ),dist ( n ),centers ( n ),removed ( n ),childs ( n,-1 ), found ( n ) { int m=1; height=1; while ( m<n ) { m*=2; height++; } decompose(); } int fillChilds ( int r, int p ) { // cout<<r<<" "<<n<<endl; if ( childs[r]>0 ) return childs[r]; int ch=0; for ( pii pi: adj[r] ) if ( pi.first!=p ) ch+=1+fillChilds ( pi.first,r ); childs[r]=ch; return ch; } void findDists ( int r ) { if ( found[r] ) { found=vector<bool> ( n ); // cout<<"reset found"<<endl; } priority_queue<pii> pq; pq.push ( mp ( 0,r ) ); while ( !pq.empty() ) { pii nxt=pq.top(); int j=nxt.second; int d=nxt.first; pq.pop(); if ( found[j] ) continue; found[j]=1; dist[j].push_back ( nxt.first ); centers[j].push_back ( r ); for ( pii pi: adj[j] ) { if ( !removed[pi.first] && !found[pi.first] ) pq.push ( mp ( d+pi.second,pi.first ) ); } } } void decompose() { int r=0; fillChilds ( r,-1 ); // cout<<childs; deque<int> roots; roots.push_back ( 0 ); while ( roots.size() ) { int nxt=roots.front(); roots.pop_front(); int center=splitCenter ( nxt ); order.push_back ( center ); removed[center]=true; findDists ( center ); for ( pii pi: adj[center] ) { if ( !removed[pi.first] ) roots.push_back ( pi.first ); } } } int splitCenter ( int r ) { int m=childs[r]+1; int split=m/2+m%2; while ( true ) { int most=0; int mosti=0; for ( pii pi: adj[r] ) { int j=pi.first; if ( removed[j] ) continue; if ( childs[j]>most ) { most=childs[j]; mosti=j; } } if ( most<split ) break; childs[r]=m-most-2; r=mosti; } // cout<<"found root: "<<r<<", "<<m<<endl<<childs<<endl; return r; } int getDist ( int i, int j ) { int level=min ( centers[i].size(),centers[j].size() )-1; while ( level>0 ) { if ( centers[i][level]==centers[j][level] ) break; level--; } return dist[i][level]+dist[j][level]; } int getLevel ( int j ) { return centers[j].size()-1; } }; struct data { ll nxsum=0; ll sum=0; ll corr=0; int n=0; bool prop=0; }; ostream & operator<< ( ostream& o,data d ) { return o<<"{"<<d.nxsum<<", "<<d.sum<<", "<<d.corr<<", "<<d.n<<"}"; } int main() { ios_base::sync_with_stdio ( false ); int n,t; cin>>n>>t; // cout<<n<<t; vector<vpii> adj ( n ); rep ( i,n-1 ) { int a,b,c; cin>>a>>b>>c; a--; b--; adj[a].push_back ( mp ( b,c ) ); adj[b].push_back ( mp ( a,c ) ); } CentroidDecomp dec ( adj ); vector<data> ds ( n ); rep ( ixx,t ) { int m; ll su=0; cin>>m; vi nod; rep ( i,m ) { int j; cin>>j; nod.push_back ( j-1 ); } if ( m>20 ) { sort ( all ( nod ) ); int last=-1; vi nodes; vector<pii> nodesM; for ( int j: nod ) { if ( j==last ) nodesM.back().second+=1; else { last=j; nodes.push_back ( j ); nodesM.push_back ( mp ( j,1 ) ); } } vector<vector<int>> levels ( 20 ); int maxl=0; for ( int j: nodes ) { int L=dec.centers[j].size(); maxl=max ( maxl,L ); rep ( l,L ) { levels[l].push_back ( j ); } } rep ( l,maxl ) { auto it=unique ( all ( levels[l] ) ); levels[l].resize ( it-levels[l].begin() ); } for ( int j: nodes ) { rep ( l,dec.centers[j].size() ) { ds[dec.centers[j][l]]=data(); } } for ( const pii p:nodesM ) { int k=p.first; ds[p.first].n=p.second; rep ( l,dec.centers[k].size()-1 ) { int d=dec.dist[k][l]; data &dc=ds[dec.centers[k][l+1]]; dc.nxsum+= ( ll ) d*p.second; } } for ( int l=maxl; l>0; l-- ) { for ( int k: levels[l] ) { data &dc=ds[dec.centers[k][l]]; if ( !dc.prop ) { dc.prop=1; ll su=dc.sum* ( dc.n-1 ) +dc.corr; data &da=ds[dec.centers[k][l-1]]; da.sum+=dc.nxsum; da.corr+=su; da.corr-=dc.nxsum* ( dc.n-1 ); da.n+=dc.n; } } } // cout<<ds<<endl; int root=dec.order[0]; data rd=ds[root]; // cout<<rd.n<<endl; // assert ( rd.n==m ); su=rd.sum* ( rd.n-1 ) +rd.corr; } else { rep ( i,nod.size() ) rep ( j,i ) { su+=dec.getDist ( nod[i],nod[j] ); } } cout<<su<<"\n"; } }