#include <cstdio> #include <vector> #include <algorithm> using namespace std; struct edge { int nod,c; edge(int nod1,int c1) {nod=nod1;c=c1;} }; struct arbint { int s,lazy; }arb[400010]; vector<edge> v[100010]; int niv[100010],first[100010],last[100010],aib[100010],v1[1000010],nr; int lant[100010],tata[100010],maxx[100010],trecut[100010],size[100010],poz[100010],sizelant[100010],nrlant; int v2[100010],v3[100010],rez; int niv1[100010],tata1[100010][20],logn; char vaz[100010]; void dfs(int nod,int lev) { vaz[nod]=size[nod]=1; first[nod]=++nr; niv[nod]=lev; for(vector<edge>::iterator it=v[nod].begin();it!=v[nod].end();it++) if(!vaz[it->nod]) { //tata1[it->nod][0]=nod; niv1[it->nod]=niv1[nod]+1; dfs(it->nod,lev+it->c); size[nod]+=size[it->nod]; } last[nod]=nr; } void dfs1(int nod,int l) { vaz[nod]=1; lant[nod]=l; poz[nod]=++sizelant[l]; int fiu=0; for(vector<edge>::iterator it=v[nod].begin();it!=v[nod].end();it++) if(!vaz[it->nod] && size[it->nod]>size[fiu]) fiu=it->nod; if(!fiu) return; dfs1(fiu,l); for(vector<edge>::iterator it=v[nod].begin();it!=v[nod].end();it++) if(!vaz[it->nod]) { ++nrlant; tata[nrlant]=nod; dfs1(it->nod,nrlant); } } void aib_update(int i,int s) { for(;i<=nr;i+=i&(-i)) aib[i]+=s; } int aib_query(int i) { int s=0; for(;i>0;i-=i&(-i)) s+=aib[i]; return s; } void update(int nod,int st,int dr) { if(niv1[arb[nod].lazy]>niv1[arb[nod].s]) arb[nod].s=arb[nod].lazy; if(st<dr) { if(niv1[arb[nod].lazy]>niv1[arb[nod*2].lazy]) arb[nod*2].lazy=arb[nod].lazy; if(niv1[arb[nod].lazy]>niv1[arb[nod*2+1].lazy]) arb[nod*2+1].lazy=arb[nod].lazy; } arb[nod].lazy=0; } void arbint_update(int nod,int st,int dr,int left,int right,int val) { if(left<=st && dr<=right) { if(niv1[val]>niv1[arb[nod].lazy]) arb[nod].lazy=val; update(nod,st,dr); return; } update(nod,st,dr); int mid=(st+dr)/2; if(left<=mid) arbint_update(nod*2,st,mid,left,right,val); else update(nod*2,st,mid); if(mid<right) arbint_update(nod*2+1,mid+1,dr,left,right,val); else update(nod*2+1,mid+1,dr); if(niv1[arb[nod*2].s]>niv1[arb[nod*2+1].s]) arb[nod].s=arb[nod*2].s; else arb[nod].s=arb[nod*2+1].s; } void arbint_query(int nod,int st,int dr,int poz) { update(nod,st,dr); if(st==dr) { rez=arb[nod].s; return; } int mid=(st+dr)/2; if(poz<=mid) arbint_query(nod*2,st,mid,poz); else arbint_query(nod*2+1,mid+1,dr,poz); } void update_refresh(int nod,int st,int dr) { arb[nod].s=arb[nod].lazy=0; if(st<dr) arb[nod*2].s=arb[nod*2].lazy=arb[nod*2+1].s=arb[nod*2+1].lazy=0; } void arbint_refreh(int nod,int st,int dr,int left,int right) { if(left<=st && dr<=right) { arb[nod].s=arb[nod].lazy=0; update_refresh(nod,st,dr); return; } update_refresh(nod,st,dr); int mid=(st+dr)/2; if(left<=mid) arbint_refreh(nod*2,st,mid,left,right); else update_refresh(nod*2,st,mid); if(mid<right) arbint_refreh(nod*2+1,mid+1,dr,left,right); else update_refresh(nod*2+1,mid+1,dr); arb[nod].s=arb[nod].lazy=0; } void arbint_refreh1(int nod,int st,int dr,int poz) { update_refresh(nod,st,dr); if(st==dr) { arb[nod].s=arb[nod].lazy=0; return; } int mid=(st+dr)/2; if(poz<=mid) arbint_refreh1(nod*2,st,mid,poz); else arbint_refreh1(nod*2+1,mid+1,dr,poz); arb[nod].s=arb[nod].lazy=0; } int lca(int x,int y) { if(niv1[x]<niv1[y]) swap(x,y); for(int i=logn;i>=0;i--) if(niv1[tata1[x][i]]>=niv1[y]) x=tata1[x][i]; if(x==y) return x; for(int i=logn;i>=0;i--) if(tata1[x][i]!=tata1[y][i]) {x=tata1[x][i];y=tata1[y][i];} return tata1[x][0]; } int cmp(int a,int b) { return first[a]<first[b]; } int main() { //freopen("file.in", "r", stdin); //freopen("file.out", "w", stdout); int n,m,k,x,y,c; scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { scanf("%d%d%d",&x,&y,&c); v[x].push_back(edge(y,c)); v[y].push_back(edge(x,c)); } dfs(1,0); /*for(logn=1;1<<logn<=n;logn++); logn--; for(int i=1;i<=logn;i++) for(int j=1;j<=n;j++) tata1[j][i]=tata1[tata1[j][i-1]][i-1];*/ for(int i=1;i<=n;i++) vaz[i]=0; ++nrlant; dfs1(1,nrlant); for(int i=1;i<=m;i++) { long long sol=0; scanf("%d",&k); for(int j=1;j<=k;j++) { scanf("%d",&v1[j]); sol+=niv[v1[j]]; aib_update(first[v1[j]],1); } sol=sol*(2*k-2); for(int j=1;j<=k;j++) { int nod=v1[j]; maxx[lant[nod]]=max(maxx[lant[nod]],poz[nod]); while(lant[nod]!=1) { nod=tata[lant[nod]]; maxx[lant[nod]]=max(maxx[lant[nod]],poz[nod]); } } int nr2=0; for(int j=1;j<=k;j++) { int nod=v1[j]; while(lant[nod]!=1) { int nod1=tata[lant[nod]]; if(trecut[nod1]==-1) break; if(!trecut[nod1]) { trecut[nod1]=lant[nod]; if(maxx[lant[nod1]]>poz[nod1]) { v2[++nr2]=nod1; trecut[nod1]=-1; } } else if(trecut[nod1]!=lant[nod]) { v2[++nr2]=nod1; trecut[nod1]=-1; break; } else break; nod=nod1; } } for(int j=1;j<=k;j++) if(trecut[v1[j]]!=-1) { v2[++nr2]=v1[j]; trecut[v1[j]]=-1; } /*for(int j=1;j<=nr2;j++) if(first[v2[j]]<last[v2[j]]) arbint_update(1,1,nr,first[v2[j]]+1,last[v2[j]],v2[j]); for(int j=1;j<=nr2;j++) { rez=0; arbint_query(1,1,nr,first[v2[j]]); int a=aib_query(last[v2[j]])-aib_query(first[v2[j]]-1); sol-=1LL*(niv[v2[j]]-niv[v2[rez]])*a*(2*a-2); } for(int j=1;j<=nr2;j++) { if(first[v2[j]]<last[v2[j]]) arbint_refreh(1,1,nr,first[v2[j]]+1,last[v2[j]]); arbint_refreh1(1,1,nr,first[v2[j]]); }*/ sort(v2+1,v2+1+nr2,cmp); if(v2[1]!=1) { for(int j=nr2;j;j--) v2[j+1]=v2[j]; v2[1]=1; } int nr3=0; v3[++nr3]=1; for(int j=2;j<=nr2;j++) { while(last[v3[nr3]]<first[v2[j]]) nr3--; int a=aib_query(last[v2[j]])-aib_query(first[v2[j]]-1); sol-=1LL*(niv[v2[j]]-niv[v3[nr3]])*a*(2*a-2); v3[++nr3]=v2[j]; } for(int j=1;j<=k;j++) { aib_update(first[v1[j]],-1); int nod=v1[j]; maxx[lant[nod]]=trecut[nod]=0; while(lant[nod]!=1) { nod=tata[lant[nod]]; maxx[lant[nod]]=trecut[nod]=0; } } /*long long sol1=0; for(int j=1;j<=k;j++) for(int q=j+1;q<=k;q++) sol1+=niv[v1[j]]+niv[v1[q]]-2*niv[lca(v1[j],v1[q])];*/ printf("%lld\n",sol/2); } return 0; }