#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define INPUT freopen("world.inp","r",stdin) #define OUTPUT freopen("world.out","w",stdout) #define FOR(i,l,r) for(auto i=l;i<=r;i++) #define REP(i,l,r) for(auto i=l;i<r;i++) #define FORD(i,l,r) for(auto i=l;i>=r;i--) #define REPD(i,l,r) for(auto i=l;i>r;i--) #define ENDL printf("\n") #define debug 1 typedef long long ll; typedef pair<int,int> ii; const int inf=1e9; const int MOD=1e9+7; const int N=1e5+10; int q[N],p[N],idx[N],w[N],a[1000005],d[N],v[N][2],h[N],mark[N],n,test,f[20][N<<1],lv[N],lg2[N<<1]; ll b[N<<2]; vector <int> e[N]; bool comp(int x,int y){ return lv[x]<lv[y]; } void BFS(){ q[1]=1; lv[1]=1; int top=1,bot=1; while (top<=bot){ int x=q[top++]; for(auto i:e[x]) if (i!=p[x]){ int y=v[i][0]+v[i][1]-x; q[++bot]=y,p[y]=i,d[y]=d[x]+w[i],lv[y]=lv[x]+1; } } FOR(x,1,n){ int m1=e[x].end()-e[x].begin(); REP(i,0,m1){ if (e[x][i]==p[x]){ swap(e[x][i--],e[x][--m1]); e[x].pop_back(); continue; } } } } void DFS(int x){ static int top=0; idx[x]=++top; f[0][top]=x; for(auto i:e[x]){ int y=v[i][0]+v[i][1]-x; DFS(y); f[0][++top]=x; } } int LCA(int x,int y){ x=idx[x],y=idx[y]; if (x>y) swap(x,y); int bar=lg2[y-x+1]; return min(f[bar][x],f[bar][y-(1<<bar)+1],comp); } void prepare(){ scanf("%d%d",&n,&test); int x,y; FOR(i,1,n-1){ scanf("%d%d%d",&x,&y,w+i); v[i][0]=x;v[i][1]=y; e[x].push_back(i); e[y].push_back(i); } BFS(); // printf("tick"); v[0][1]=1; DFS(1); FOR(lay,1,18) FOR(i,1,n*2-(1<<lay)) f[lay][i]=min(f[lay-1][i],f[lay-1][i+(1<<(lay-1))],comp); FOR(i,2,n<<1) lg2[i]=lg2[i>>1]+1; // printf("tick\n"); // REP(i,1,n<<1) printf("%d ",f[i][0]);ENDL; // FOR(i,1,n) printf("%d ",idx[i]);ENDL; // FOR(i,1,n) printf("%d ",lv[i]);ENDL; // FOR(i,1,n) printf("%d ",head[i]);ENDL; // FOR(i,1,n) printf("%d ",sum[i]);ENDL; } int main(){ prepare(); int n1; FOR(te,1,test){ scanf("%d",&n1); int n2=n1; FOR(i,1,n1) { scanf("%d",a+i); h[a[i]]++; if (mark[a[i]]==te) i--,n1--; mark[a[i]]=te; } ll ans=0; if (n1>=750){ FORD(i,n,1){ int x=q[i],y=v[p[x]][0]+v[p[x]][1]-x; h[y]+=h[x]; ans+=1LL*w[p[x]]*h[x]*(n2-h[x]); } memset(h,0,sizeof(h)); }else{ REP(i,1,n1) FOR(j,i+1,n1) { // printf("%d %d %d\n",a[i],a[j],LCA(a[i],a[j])); ans+=1LL*h[a[i]]*h[a[j]]*(d[a[i]]+d[a[j]]-2*d[LCA(a[i],a[j])]); } FOR(i,1,n1) h[a[i]]=0; } printf("%lld\n",ans); } }