#include <bits/stdc++.h> #define optimizar ios_base::sync_with_stdio(0); cin.tie(0) using namespace std; #define fst first #define snd second #define mp(x,y) make_pair(x,y) typedef long long int lint; const int MaxN=100001; int pot[MaxN*3],pt[64],vis[MaxN]; int table[MaxN*3][20],cmp[MaxN*3],sz; int conv[MaxN*3],H[MaxN],hashi[MaxN],root,r[MaxN]; lint dist[MaxN],B[MaxN*10+1]; vector<int>ady[MaxN]; vector<lint>adyd[MaxN]; void arr(int A[],int n){ for(int i=0;i<n;i++)cmp[i]=A[i]; sz=n; } void build(){ int i,j,p,q,x,y; for(i=1,j=0;i<sz;i*=2,j++) pot[i]=j,pt[j]=i; for(i=2;i<sz;i++) if(!pot[i])pot[i]=pot[i-1]; for(i=0;i<sz;i++) table[i][0]=i; for(p=1,q=1;p<sz;p*=2,q++){ for(i=0;i+p<sz;i++){ x=table[i][q-1]; y=table[i+p][q-1]; table[i][q]=H[cmp[x]]<H[cmp[y]]?x:y; } } } int query(int x,int y){ int p=pot[y-x+1],a,b; a=table[x][p]; b=table[y-pt[p]+1][p]; return H[cmp[a]]<H[cmp[b]]?a:b; } void posorden(){ stack<pair<int,int> >pos; int a,b=0,i,j; memset(vis,0,sizeof(vis)); pos.push(mp(root,0)); while(!pos.empty()){ a=pos.top().fst; j=pos.top().snd; if(vis[a]==ady[a].size()) conv[b++]=a,pos.pop(); else { conv[b++]=a; for(;vis[a]<ady[a].size();vis[a]++){ if(ady[a][vis[a]]!=j){ pos.push(mp(ady[a][vis[a]],a)); break; } } if(vis[a]==ady[a].size())pos.pop(); else vis[a]++; } } arr(conv,b); } void deph(){ queue<pair<int,int> >h; h.push(make_pair(root,0)); memset(vis,0,sizeof(vis)); int a,i,b; vis[root]=1,H[root]=0; while(!h.empty()){ a=h.front().first; b=h.front().second; h.pop(); for(i=0;i<ady[a].size();i++){ if(!vis[ady[a][i]]){ vis[ady[a][i]]=1; H[ady[a][i]]=b+1; dist[ady[a][i]]=dist[a]+adyd[a][i]; h.push(make_pair(ady[a][i],b+1)); } } } } void reord(){ int i,j,p,q; memset(hashi,-1,sizeof(hashi)); for(i=0;i<sz;i++){ if(hashi[cmp[i]]==-1) hashi[cmp[i]]=i; } } lint sum(int x,int y){ lint p,q,j; p=hashi[x]; q=hashi[y]; j=cmp[query(min(p,q),max(p,q))]; return dist[x]+dist[y]-2*dist[j]; } lint resp = 0; int cuantos = 0; lint sumLCA = 0; lint acumulado = 0; int cont_LCA[MaxN]; int visitados[MaxN]; int color; lint need[MaxN]; int padre[MaxN]; void busca(int nodo) { visitados[nodo] = color; if(need[nodo]) { resp+= need[nodo] * (acumulado + (cuantos * dist[nodo]) - (2 * sumLCA)); cuantos+= need[nodo]; sumLCA+= dist[nodo] * need[nodo]; cont_LCA[nodo]+= need[nodo]; acumulado+= dist[nodo] * need[nodo]; } for(int i = 0; i < ady[nodo].size(); i++) { if(visitados[ady[nodo][i]] != color) { padre[ady[nodo][i]] = nodo; busca(ady[nodo][i]); } } sumLCA-= cont_LCA[nodo] * dist[nodo]; cont_LCA[padre[nodo]]+= cont_LCA[nodo]; sumLCA+= cont_LCA[nodo] * dist[padre[nodo]]; cont_LCA[nodo] = 0; } int main(){ optimizar; lint n,i,a,b,p,q,lca,T,k,j,S; cin>>n>>T; for(i=1;i<n;i++){ cin>>a>>b>>p; ady[a].push_back(b); ady[b].push_back(a); adyd[a].push_back(p); adyd[b].push_back(p); } root=1; posorden(); deph(); reord(); build(); for(i=0;i<T;i++){ resp = sumLCA = acumulado = cuantos = 0; color++; cin>>k; for(j=0;j<k;j++) { cin>>B[j]; need[B[j]]++; } if(k <= 1300) { S=0; for(p=0;p<k;p++)for(q=p+1;q<k;q++){ S+=sum(B[p],B[q]); } cout<<S<<"\n"; } else { busca(1); cout << resp << "\n"; } for(j=0;j<k;j++) { need[B[j]]--; } } }