// GSKHIRTLADZE #include<vector> #include<iostream> #include<math.h> #include<algorithm> #include<set> #define pb push_back #define LL long long #define N 1000020 using namespace std; vector < int > g[N],s[N]; int P[N][18],D[N][18]; int in[N],out[N],timer; int n,t,a,b,c,i,j,k; int ALL[N],XX[N]; LL res; int LVL[N]; void go(int p,int u) { timer++; in[u]=timer; LVL[u] = 1 + LVL[p]; for (int k=1;k<=17;k++) P[u][k]=P[P[u][k-1]][k-1], D[u][k]=D[u][k-1]+D[P[u][k-1]][k-1]; for (int i=0;i<g[u].size();i++) { int to=g[u][i]; if (to == p) continue; D[to][0]=s[u][i]; P[to][0]=u; go(u,to); } out[u]=timer++; } int path(int u) { int ans=0; for (int i=17;i>=0;i--) if (P[u][i]) { ans+=D[u][i]; u=P[u][i]; } return ans; } int lca(int a,int b) { for (int i=17;i>=0;i--) if (P[b][i]) if (!(in[P[b][i]] <= in[a] && out[a] <= out[P[b][i]])) b=P[b][i]; if (in[b] <= in[a] && out[a] <= out[b]) return b; return P[b][0]; } bool cmp(int a,int b){ return LVL[abs(a)] > LVL[abs(b)]; } bool cmp1(int a,int b){ return in[a] < in[b]; } long long SUM[N]; vector<long long> CC(N); int LCG[N]; int tab[N]; int main(){ scanf("%d%d",&n,&t); for (i=1;i<n;i++) { scanf("%d%d%d",&a,&b,&c); s[a].pb(c); s[b].pb(c); g[a].pb(b); g[b].pb(a); } go(0,1); for (i=1;i<=n;i++) ALL[i]=path(i); while (t--) { scanf("%d",&k); vector<int> gio(k); for (i=1;i<=k;i++) scanf("%d",&XX[i]),gio[i-1] = XX[i]; sort(XX+1, XX + 1 + k,cmp); for(auto cur : gio){ CC[cur] = 0; SUM[cur] = 0; } for(auto cur : gio){ CC[cur] ++; } for(auto got : gio) tab[got]=1; sort(gio.begin(),gio.end(),cmp1); gio.resize(unique(gio.begin(),gio.end())-gio.begin()); int sz = gio.size(); for(int i = 0; i < sz-1; i++) { gio.push_back(lca(gio[i],gio[i+1])); } vector<int> stack; sort(gio.begin(),gio.end(),cmp1); gio.resize(unique(gio.begin(),gio.end())-gio.begin()); for(auto cur : gio){ while(stack.size() != 0 && !(in[stack.back()]< in[cur] && out[stack.back()]>=out[cur])) stack.pop_back(); if(stack.size()){ LCG[cur] = stack.back(); }else{ LCG[cur] = -1; } stack.push_back(cur); } long long res =0; sort(gio.begin(),gio.end(),cmp); gio.resize(unique(gio.begin(),gio.end())-gio.begin()); for(int cur : gio){ int par = LCG[cur]; if(par == -1) continue; long long dist = (ALL[cur] - ALL[par]) * CC[cur] + SUM[cur]; res += dist * CC[par] + SUM[par] * CC[cur]; //cout<<"cur :"<<cur<<" par : "<<par<<' '<<dist * CC[par] + SUM[par] * CC[cur]<<" res: "<<res<<endl; CC[par]+=CC[cur]; SUM[par] += dist; } for(auto cur : gio){ LCG[cur] = CC[cur] = SUM[cur] = 0; tab[cur]=0; } cout<<res<<endl; res=0; } }