// Coded by: samfisher #include<bits/stdc++.h> #define ll long long int #define vii vector<int>::iterator #define vli vector<ll>::iterator #define vi vector<int> #define vl vector<ll> #define pb(x) push_back(x) #define pf(x) push_front(x) #define mp(x,y) make_pair(x,y) #define MOD 1000000007 #define in cin>> #define i2(x,y) cin>>x>>y #define i3(x,y,z) cin>>x>>y>>z #define os(x) cout<<x<<' ' #define on(x) cout<<x<<endl #define o2(x,y) cout<<x<<' '<<y<<endl #define o3(x,y,z) cout<<x<<' '<<y<<' '<<z<<endl #define pn cout<<endl #define F first #define S second #define for_it(it, X) for (__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++) #define op(X) cout<<X.F<<" "<<X.S<<" "; #define opn(X) cout<<X.F<<" "<<X.S<<endl; using namespace std; vector< pair<int,int> > edge[100009]; int parent[100009][32]; int start[100009]; int tmp[100009]; int dist[100009]; int inverse[100009]; int depth[100009]; int G=0; void dfs(int cur,int dep,int dis) { int i=1,j=1; if(start[cur]!=0) return; start[cur]=++G; if(depth == 0) parent[cur][1]=cur; for(i=0;i<32;i++) parent[cur][i]=-1; parent[cur][0] = cur; dist[cur] = dis; depth[cur] = dep; tmp[dep] = cur; // o2(cur, depth[cur]); i=1; j=1; inverse[cur] = G; while(i<=dep) { parent[cur][j] = tmp[dep - i]; i*=2; j++; } for(i=0; i<edge[cur].size();i++) { dfs(edge[cur][i].F,dep+1, dis+edge[cur][i].S); } } int LCA(int a, int b) { // o3("Enter LCA",a,b); int x,y,i; // o3("Given ",a,b); assert(a>0); assert(b>0); if(depth[a]<depth[b]) swap(a,b); while(depth[a]>depth[b]) { for(i=0;depth[parent[a][i]]>=depth[b] && parent[a][i]!=-1;i++) ; a=parent[a][i-1]; } // o3(" Normalized ",a,b); if(a==b) { // o2("Exit",a); return a; } while(1) { for(i=0;parent[a][i]!=parent[b][i];i++); a = parent[a][i-1]; b = parent[b][i-1]; if(parent[a][1]==parent[b][1]) { // o2("Exit",parent[a][1]); return parent[a][1]; } } } typedef struct node{ int cnt; int left; int cur; int l,r; }node; ll ans=0; void print(node A) { // o2("Printing Node",A.cur); // o3(A.cnt, A.l, A.left); } int main() { ios_base::sync_with_stdio(false); int t,i,j,k,n,m,a,b,c,q; i2(n,q); for(i=1;i<n;i++) { i3(a,b,c); edge[a].pb(mp(b,c)); edge[b].pb(mp(a,c)); } dfs(1,0,0); while(q--) { in k; ans=0; vector< pair<int,int> > A(k); for(i=0;i<k;i++) { in j; A[i]=mp(inverse[j],j); } sort(A.begin(), A.end()); vector< node > B(k); priority_queue< pair<int,int> > Q; for(i=0;i<k;i++) { B[i].cnt=1; B[i].cur=A[i].S; B[i].l = i-1; if(B[i].l==-1) B[i].left = -1; else B[i].left = depth[LCA(A[i-1].S,A[i].S)]; // print(B[i]); Q.push(mp(B[i].left, i)); } int c,d; while(!Q.empty()) { a=Q.top().F; b=Q.top().S; Q.pop(); if(B[b].cur==-1 || B[b].l == -1) continue; c=B[b].l; // o3("Combinng",B[b].cur,B[c].cur); B[b].l = B[c].l; print(B[b]); print(B[c]); d = LCA(B[b].cur, B[c].cur); ans += (k-B[c].cnt)*1ll*(B[c].cnt)*(dist[B[c].cur] - dist[d]); ans += (k-B[b].cnt)*1ll*(B[b].cnt)*(dist[B[b].cur] - dist[d]); B[c].cur =-1; B[c].l = -1; B[b].cnt+=B[c].cnt; B[b].cur=d; if(B[b].l != -1) { B[b].left = depth[LCA(B[B[b].l].cur ,B[b].cur )]; Q.push(mp(B[b].left, b)); } // o2("Finally",ans); print(B[b]); } on(ans); } }