#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(i=a;i<b;++i) #define repi(i,a,b) for(int i=a;i<b;++i) #define F first #define S second #define mp(a,b) make_pair(a,b) #define pii pair<int,int> #define ppi pair<pii,int> #define ppp pair<pii,pii> #define vi vector<int> #define sc(a) fasti(a) #define pb(a) push_back(a) #define DEBUG12 #define LOGMAX 15 #define getc getchar_unlocked #define putc(x) putchar_unlocked(x) inline void fasti(int &x) { char temp; temp = getc(); x = 0; while(temp<='9' && temp>='0') { x=(x<<3) + (x<<1) + temp - '0'; temp = getc(); } } int n,t; vector<pii> e[100001]; int dist[100001]; vector<pii> g[100001]; //LCA... int dep[100001]; int P[100001][20]; int T[100001]; int N; inline void One(int root=1,int father=0,int depth=0) { dep[root]=depth; T[root]=father; for (int i=0;i<g[root].size();++i) { if (g[root][i].F==father) continue; One(g[root][i].F,root,depth+1); } } inline void Build() { memset(P,-1,sizeof P); for (int i=1;i<=N;i++) P[i][0]=T[i]; for (int j=1;j<=LOGMAX;j++) { for (int i=1;i<=N;i++) { if (P[i][j-1]!=-1) P[i][j]=P[ P[i][j-1] ][j-1]; } } } inline int LCA(int v,int u) { if (dep[v]>dep[u]) swap(v,u); int up=dep[u]-dep[v]; for (int i=LOGMAX;i>=0;i--) { if ((1<<i)<=up) { up-=(1<<i); u=P[u][i]; } } if (v==u) return u; for (int i=LOGMAX;i>=0;i--) { if (P[u][i]!=P[v][i]) u=P[u][i],v=P[v][i]; } return T[u]; } //LCA END... //input and convert int post[100001]; int invpost[100001]; inline void inp() { sc(n); N=n; sc(t); repi(i,0,n-1) { int a,b,c; sc(a); sc(b); sc(c); g[a].pb(mp(b,c)); g[b].pb(mp(a,c)); } } inline void calcdist(int node=1, int parent=0, int dis = 0) { dist[node] = dis; static int po = 0; for(auto ne : g[node]) { if(ne.F == parent) continue; calcdist(ne.F, node, dis + ne.S); } ++po; post[node] = po; invpost[po] = node; } //input and convert... end //solve set<int> anslocs; set<pair<int,pair<int,int>>> depthset; pair<int, long long int> inter[100001]; long long ans = 0; int k; inline void solvem() { auto iter = anslocs.begin(); auto iter2 = anslocs.begin(); ++iter2; for(;iter2!=anslocs.end();++iter,++iter2) { depthset.insert(mp(dep[LCA(invpost[*iter],invpost[*iter2])],mp(*iter,*iter2))); } while(anslocs.size()>1) { int a,b,temp; auto iterk = depthset.rbegin(); auto ds = *iterk; depthset.erase(next(iterk).base()); a = invpost[ds.S.F]; b = invpost[ds.S.S]; auto iter_1 = anslocs.find(ds.S.F); auto iter_2 = anslocs.find(ds.S.S); if(iter_1 != anslocs.begin()) { auto itertemp = iter_1; --itertemp; depthset.erase(mp(dep[LCA(invpost[*iter_1],invpost[*itertemp])],mp(*itertemp,*iter_1))); } if(iter_2 != next(anslocs.rbegin()).base()) { auto itertemp = iter_2; ++itertemp; depthset.erase(mp(dep[LCA(invpost[*iter_2],invpost[*itertemp])],mp(*iter_2,*itertemp))); } anslocs.erase(iter_1); anslocs.erase(iter_2); #ifdef DEBUG1 printf("anslocs chose: %d, %d\n",a,b); printf("which are %d,%lld, %d,%lld\n",inter[a].F, inter[a].S, inter[b].F, inter[b].S); for(int i : anslocs) { printf("%d, ",invpost[i]); } printf("\n"); #endif int lca = LCA(a, b); #ifdef DEBUG1 printf("lca: %d\n",lca ); #endif int e = dist[a] - dist[lca]; int f = dist[b] - dist[lca]; int A = inter[a].F; long long B = inter[a].S; int C = inter[b].F; long long D = inter[b].S; if(!anslocs.count(post[lca])) { ans += (e+f) * 1ll * A*1ll*C + A * 1ll * D + B*1ll * C; inter[lca] = mp(A+C, B+D+C*1ll*f + A*1ll*e); anslocs.insert(post[lca]); auto itert = anslocs.find(post[lca]); if(itert != anslocs.begin()) { auto itert2 = itert; --itert2; depthset.insert(mp(dep[LCA(invpost[*itert2],invpost[*itert])],mp(*itert2,*itert))); } if(itert != next(anslocs.rbegin()).base()) { auto itert2 = itert; ++itert2; depthset.insert(mp(dep[LCA(invpost[*itert2],invpost[*itert])],mp(*itert,*itert2))); } } else { ans += (e+f) * 1ll * A*1ll* C + A * 1ll * D + B*1ll * C; pair<int, long long> temp = mp(A+C, B+D+C*1ll*f + A*1ll*e); ans += inter[lca].F*1ll*temp.S + inter[lca].S*1ll*temp.F; inter[lca] = mp(inter[lca].F + temp.F, inter[lca].S + temp.S); } /*else if (lca == a){ ans += C*f + D; inter[lca] = mp(C+A,B+D+C*f); anslocs.insert(lca); } else if(lca == b) { ans += A*e + B; inter[lca] = mp(A+C,B+D+A*e); anslocs.insert(lca); } else { assert(false); }*/ #ifdef DEBUG1 printf("ans: %lld\n",ans); printf("lca now %d, %lld\n",inter[lca].F,inter[lca].S); #endif } } inline void solve() { repi(i,0,t) { sc(k); repi(j,0,k) { int x; ans = 0; sc(x); if(anslocs.count(post[x])) { inter[x] = mp(inter[x].F+1,0); } else { inter[x] = mp(1,0); } anslocs.insert(post[x]); } solvem(); printf("%lld\n",ans); anslocs.clear(); } } //solve. int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ inp(); //changegraph(); #ifdef DEBUG1 repi(i,1,n+1) { printf("%d -->> ",i); for(auto x : g[i]) { printf("(%d, %d), ",x.F,x.S); } printf("\n"); } repi(i,1,n+1) { printf("post %d: %d\n",i,post[i]); } repi(i,1,n+1) { printf("%d -->> ",i); for(auto x : e[i]) { printf("(%d, %d), ",x.F,x.S); } printf("\n"); } #endif int tttt = (rand() % N) + 1; One(tttt,0,0); Build(); calcdist(tttt); solve(); return 0; }