#include <cstdlib> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cmath> #include <stack> #include <map> #include <set> #include <deque> #include <cstring> #include <functional> #include <climits> #include <list> #include <ctime> #include <complex> #define F1(x,y,z) for(int x=y;x<z;x++) #define F2(x,y,z) for(int x=y;x<=z;x++) #define F3(x,y,z) for(int x=y;x>z;x--) #define F4(x,y,z) for(int x=y;x>=z;x--) #define pb push_back #define LL long long #define co complex<double> #define MAX 100005 #define AMAX 16384 #define MOD 1000000007 #define f(c,d) ((1<<(c))*(d)) using namespace std; int n,m,ta,tb,tc,en[MAX],ei,par[MAX],ra[MAX],anc[MAX],rt,vv[MAX],dp[MAX],ki[MAX],kt[MAX]; LL d[MAX],ans; bool v[MAX]; vector<int> va[MAX],vb[MAX]; vector<int> lca1[MAX],lca2[MAX],lca3[MAX]; vector<vector<pair<int,int> > > k; vector<vector<int> > klca,vl,kcnt,kk; stack<int> x; void dfs1(int a,int b,LL e){ //printf("%d from %d\n",a,b); d[a]=e; F1(c,0,va[a].size())if(va[a][c]!=b)dfs1(va[a][c],a,e+vb[a][c]); en[a]=ei++; } int find(int a){ if(par[a]==a)return a; return par[a]=find(par[a]); } void uni(int a,int b){ find(a); find(b); if(ra[par[a]]>ra[par[b]])par[par[b]]=par[a]; else if(ra[par[a]]<ra[par[b]])par[par[a]]=par[b]; else{ par[par[b]]=par[a]; ra[a]++; } } void dfs2(int a,int b){ par[a]=a; ra[a]=0; anc[a]=a; F1(c,0,va[a].size())if(va[a][c]!=b){ dfs2(va[a][c],a); uni(a,va[a][c]); anc[find(a)]=a; } v[a]=1; F1(c,0,lca1[a].size())if(v[lca1[a][c]]){ klca[lca2[a][c]][lca3[a][c]]=anc[find(lca1[a][c])]; } } void dfs3(int a,int b){ // printf("dfs3 %d %d\n",a,b); dp[a]=ki[a]==tb?kt[a]:0; F1(c,0,vl[vv[a]].size())if(vl[vv[a]][c]!=b){ dfs3(vl[vv[a]][c],a); dp[a]+=dp[vl[vv[a]][c]]; // printf("%d %d %lld %lld %d %d %lld\n",a,vl[vv[a]][c],d[a],d[vl[vv[a]][c]],dp[vl[vv[a]][c]],ta,(d[vl[vv[a]][c]]-d[a])*dp[vl[vv[a]][c]]*(ta-dp[vl[vv[a]][c]])); ans+=(d[vl[vv[a]][c]]-d[a])*dp[vl[vv[a]][c]]*(ta-dp[vl[vv[a]][c]]); } } int main(){ scanf("%d%d",&n,&m); F1(a,1,n){ scanf("%d%d%d",&ta,&tb,&tc); va[ta].pb(tb); vb[ta].pb(tc); va[tb].pb(ta); vb[tb].pb(tc); } dfs1(1,0,0); //F2(a,1,n)printf("%d %d\n",a,en[a]); while(m--){ scanf("%d",&ta); k.pb(vector<pair<int,int> >()); kk.pb(vector<int>()); kcnt.pb(vector<int>()); while(ta--){ scanf("%d",&tb); k.back().pb(make_pair(en[tb],tb)); } sort(k.back().begin(),k.back().end()); kk.back().pb(k.back()[0].second); kcnt.back().pb(1); F1(a,1,k.back().size()){ if(k.back()[a].second==kk.back().back())kcnt.back().back()++; else{ kk.back().pb(k.back()[a].second); kcnt.back().pb(1); } } } //F1(a,0,k.size())F1(b,0,k[a].size())printf("%d%c",k[a][b].second,b==k[a].size()-1?'\n':' '); F1(a,0,kk.size()){ klca.pb(vector<int>()); F1(b,1,kk[a].size()){ klca.back().pb(0); lca1[kk[a][b-1]].pb(kk[a][b]); lca2[kk[a][b-1]].pb(a); lca3[kk[a][b-1]].pb(b-1); lca1[kk[a][b]].pb(kk[a][b-1]); lca2[kk[a][b]].pb(a); lca3[kk[a][b]].pb(b-1); } } dfs2(1,0); //F1(a,0,k.size())F1(b,0,klca[a].size())printf("%d%c",klca[a][b],b==klca[a].size()-1?'\n':' '); F1(a,0,kk.size()){ //F1(b,0,kk[a].size())printf("%d%c",-kk[a][b],b==kk[a].size()-1?'\n':' '); ans=0; vl.clear(); vl.pb(vector<int>()); vv[kk[a][0]]=vl.size(); vl.pb(vector<int>()); //printf("-\n"); rt=kk[a][0]; x=stack<int>(); x.push(kk[a][0]); // F2(c,1,n)printf("%d%c",vv[c],c==n?'\n':' '); F1(b,1,kk[a].size()){ if(klca[a][b-1]!=kk[a][b]){ vv[kk[a][b]]=vl.size(); //printf("A %d\n",b); vl.pb(vector<int>()); } if(klca[a][b-1]==kk[a][b-1]){ //printf("B %d\n",b); vl[vv[kk[a][b-1]]].pb(kk[a][b]); x.push(kk[a][b]); }else{ ta=-1; while(!x.empty()){ if(d[x.top()]>d[klca[a][b-1]]){ // printf("pop %d\n",b); ta=x.top(); x.pop(); } else break; } if(!x.empty()){ if(d[x.top()]!=d[klca[a][b-1]]){ //printf("normal insert %d\n",b); //vv[klca[a][b-1]]=vv[x.top()]; //vv[x.top()]=vl.size(); //vl.pb(vector<int>()); //printf("--\n"); //vl.back().pb(klca[a][b-1]); vl[vv[x.top()]].pop_back(); vl[vv[x.top()]].pb(klca[a][b-1]); vv[klca[a][b-1]]=vl.size(); vl.pb(vector<int>()); if(ta!=-1){ //printf("ta %d\n",ta); vl.back().pb(ta); } x.push(klca[a][b-1]); } }else{ //printf("new rt %d\n",b); vv[klca[a][b-1]]=vl.size(); vl.pb(vector<int>()); //printf("---\n"); vl.back().pb(ta); x.push(klca[a][b-1]); rt=klca[a][b-1]; } if(klca[a][b-1]!=kk[a][b]){ //printf("tail %d\n",b); vl[vv[klca[a][b-1]]].pb(kk[a][b]); x.push(kk[a][b]); } } //F2(c,1,n)printf("%d%c",vv[c],c==n?'\n':' '); } ta=0; tb=a+1; F1(b,0,kk[a].size()){ ki[kk[a][b]]=a+1; ta+=kcnt[a][b]; kt[kk[a][b]]=kcnt[a][b]; } dfs3(rt,0); //printf("vl %d\n",vl.size()); printf("%lld\n",ans); } //system("pause"); return 0; }