#include <iostream> #include <stdio.h> #include <vector> #include <algorithm> using namespace std; typedef long long Int; int MIN(int a,int b) { if (a<b) return a; else return b; } int n,q; vector< pair<int,int> > Graph[200111]; vector< pair<int,int> > Children[200111]; int rootdist[200111]; int inctr=0; int InVal[200111]; int WhoseIn[200111]; int LastIn[200111]; int FirstSeen[200111]; int L=0; int Visits[200111]; int RMQ[18][200111]; int VAL[200111]; int GetMIN(int L,int R) { return MIN( RMQ[ VAL[R-L+1] ][L] , RMQ[ VAL[R-L+1] ][ R-(1<<VAL[R-L+1])+1 ] ); } int GetLCA(int a,int b) { int L,R; L=FirstSeen[a]; R=FirstSeen[b]; if (L>R) return WhoseIn[ GetMIN(R,L) ]; else return WhoseIn[ GetMIN(L,R) ]; } int GetDist(int a,int b) { int LCA=GetLCA(a,b); return rootdist[a]+rootdist[b]-2*rootdist[LCA]; } void DFS(int ver,int dad,int dist) { int i; rootdist[ver]=dist; inctr++; InVal[ver]=inctr; WhoseIn[inctr]=ver; L++; Visits[L]=InVal[ver]; FirstSeen[ver]=L; for (i=0;i<Graph[ver].size();i++) { if (Graph[ver][i].first==dad) continue; Children[ver].push_back(Graph[ver][i]); DFS(Graph[ver][i].first,ver,dist+Graph[ver][i].second); L++; Visits[L]=InVal[ver]; } LastIn[ver]=inctr; return; } int k; int special[200111]; int CTR[200111]; bool LTRS(int a,int b) { return InVal[a]<InVal[b]; } vector<int> Tree[200111]; vector<int> VUsed; int Build(int L,int R) { if (L==R) return special[L]; //cout<<L<<"~"<<R<<endl; int beg=L,theend; int l,r,mid,best; int root=GetLCA(special[L],special[R]); int kid,newkid; int i; VUsed.push_back(root); //cout<<"Picked root = "<<root<<endl; //cout<<"Because GETLCA of "<<special[L]<<" and "<<special[R]<<" is "<<root<<endl; while (beg<=R && special[beg]==root) { beg++; } while(beg<=R) { l=0; r=(int)Children[root].size()-1; best=-1; while(l<=r) { mid=(l+r)/2; //cout<<"Testing "<<mid<<endl; //cout<<"InVal = "<<InVal[ Children[root][mid].first ]<<endl; //cout<<"Vs special inval = "<<InVal[ special[beg] ]<<endl; if (InVal[ Children[root][mid].first ]<=InVal[ special[beg] ]) { //cout<<"Okay is "<<mid<<endl; best=mid; l=mid+1; } else r=mid-1; } kid=Children[root][best].first; //cout<<"Kid is "<<kid<<endl; for (i=beg;i<=R;i++) { if (InVal[ special[i] ]<=LastIn[kid]) theend=i; else break; } newkid=Build(beg,theend); Tree[root].push_back(newkid); //cout<<"Edge "<<root<<"~"<<newkid<<endl; beg=theend+1; } return root; } Int ans=0; int Calc(int ver,int dad) { int i; int total=CTR[ver]; for (i=0;i<Tree[ver].size();i++) { total+=Calc(Tree[ver][i],ver); } ans+=( (Int)k - (Int)total ) * ( (Int)total ) * (Int)( GetDist(ver,dad) ); return total; } int main() { int i,j; int a,b,c; int root; scanf("%d %d",&n,&q); VAL[1]=0; for (i=2;i<=200000;i++) { VAL[i]=VAL[i-1]; if ((1<<(VAL[i-1]+1))<=i) VAL[i]++; } for (i=1;i<=n-1;i++) { scanf("%d %d %d",&a,&b,&c); Graph[a].push_back(make_pair(b,c)); Graph[b].push_back(make_pair(a,c)); } DFS(1,0,0); for (i=1;i<=L;i++) { RMQ[0][i]=Visits[i]; //cout<<Visits[i]<<" "; } //cout<<endl; for (i=1;(1<<i)<=L;i++) { for (j=1;j<=L-(1<<i)+1;j++) { RMQ[i][j]=MIN( RMQ[i-1][j],RMQ[i-1][ j+(1<<(i-1)) ] ); //cout<<RMQ[i][j]<<" "; } //cout<<endl; } for (i=1;i<=q;i++) { scanf("%d",&k); for (j=1;j<=k;j++) { scanf("%d",&special[j]); CTR[ special[j] ]++; } sort(special+1,special+1+k,LTRS); VUsed.clear(); root=Build(1,k); ans=0; Calc(root,0); printf("%lld\n",ans); for (j=0;j<VUsed.size();j++) { Tree[ VUsed[j] ].clear(); } for (j=1;j<=k;j++) { CTR[ special[j] ]--; } } return 0; }