// spnauT // #include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int _b=(b),i=(a); i<_b; ++i) #define ROF(i,b,a) for(int _a=(a),i=(b); i>_a; --i) #define REP(n) for(int _n=(n); --_n>=0;) #define _1 first #define _2 second #define PB(x) push_back(x) #define SZ(x) int((x).size()) #define ALL(x) (x).begin(), (x).end() #define MSET(m,v) memset(m,v,sizeof(m)) #define MAX_PQ(T) priority_queue <T> #define MIN_PQ(T) priority_queue <T,vector<T>,greater<T>> #define IO() {ios_base::sync_with_stdio(0); cin.tie(0);} #define nl '\n' #define cint1(a) int a; cin>>a #define cint2(a,b) int a,b; cin>>a>>b #define cint3(a,b,c) int a,b,c; cin>>a>>b>>c typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<LL> VL; typedef vector<PII> VP; template<class A, class B> inline bool mina(A &x, B y) {return(y<x)?(x=y,1):0;} template<class A, class B> inline bool maxa(A &x, B y) {return(x<y)?(x=y,1):0;} typedef vector<VI> VVI; typedef pair<LL,int> PLI; typedef vector<PLI> VLI; class CentroidDecom { private: VI V, tsz, tp, st, tv, dpt; int sti, tvi, root; public: int N, A, B; VP par; VVI edge, cde; CentroidDecom(){} CentroidDecom(int a, int b, const VP &E) { A = a; B = b; N = B + 1; edge.resize(N); for(PII p: E) {edge[p._1].PB(p._2); edge[p._2].PB(p._1);} decomAll(); } CentroidDecom(int a, int b, const VI *E) { A = a; B = b; N = B + 1; edge.resize(N); memcpy(&edge[0], E, sizeof(edge[0]) * N); decomAll(); } int getRoot() const {return root;} int cdDepth(int id) { if(dpt.size() == 0) dpt.resize(N,-1); if(dpt[id] == -1) { if(par[id]._1 == id) dpt[id] = 0; else dpt[id] = cdDepth(par[id]._1) + 1; } return dpt[id]; } private: void decomAll() { V.resize(N,0); par.resize(N); cde = VVI(N); st.resize(N); tsz.resize(N); tp.resize(N); tv.resize(N); root = decom(A); par[root] = PII(root,-1); V.resize(0); st.resize(0); tsz.resize(0); tp.resize(0); tv.resize(0); } int decom(int id) {dfsSize(id); int r = findCentroid(id); decomRec(r); return r;} void dfsSize(int id) { tvi = 0; sti = -1; st[++sti] = id; tp[id] = -1; while(sti >= 0) { int u = st[sti]; if(V[u] == 0) { V[u] = 1; tsz[u] = 1; tv[tvi++] = u; for(int v: edge[u]) if(!V[v]) { tp[v] = u; st[++sti] = v; } } else { V[u] = 0; --sti; if(tp[u] != -1) tsz[tp[u]] += tsz[u]; } } } int findCentroid(int id) { int r = id, n = tvi, mmsz = n; FOR(i,0,tvi) { int u = tv[i], maxsz = n - tsz[u]; for(int v: edge[u]) if(!V[v] && tp[u] != v) maxa(maxsz, tsz[v]); if(mina(mmsz, maxsz)) r = u; } return r; } void decomRec(int r) { V[r] = 2; int i = 0; for(int v: edge[r]) if(!V[v]) { int w = decom(v); par[w] = PII(r, i++); cde[r].PB(w); } V[r] = 0; } }; #define MAXN (100004) #define MAXQ (100004) #define MAXS (1000004) #define MAXL (200004) #define MAXL2 (18) int N, Q; int C[MAXN]; VP E[MAXN]; VP EL; LL distSum; CentroidDecom T; LL tsum[MAXN]; int tcn[MAXN]; VLI tval1[MAXN]; VP A[MAXQ]; int B[MAXS]; VP QA; VI QC; int qn; int qi; PII D[MAXL]; int dn; PII D1[MAXL2][MAXL]; int DB[MAXL]; int V[MAXN]; int DI[MAXN]; int depth1[MAXN]; int depth2[MAXN]; void dfs(int u) { DI[u] = dn; D[dn++] = PII(depth1[u], u); V[u] = 1; for(PII e: E[u]) { int v = e._1; if(!V[v]) { depth1[v] = depth1[u] + 1; depth2[v] = depth2[u] + e._2; dfs(v); D[dn++] = PII(depth1[u], u); } } } void calc1() { depth1[0] = depth2[0] = 0; dfs(0); /* printf("dn %d\n", dn); FOR(i,0,dn) printf("%d ", D[i]._2+1); putchar(nl); */ FOR(i,0,dn) D1[0][i] = D[i]; FOR(i,1,MAXL2) { int s = 1<<(i-1); FOR(j,0,dn) { if(j+s >= dn) D1[i][j] = D1[i-1][j]; else D1[i][j] = min(D1[i-1][j], D1[i-1][j+s]); } } int a = 0; FOR(i,2,dn+1) { if(i == (i&-i)) ++a; DB[i] = a; } } inline int getDepth2(int a, int b) { if(a == b) return 0; int ai = DI[a]; int bi = DI[b]; if(ai > bi) { swap(ai,bi); swap(a,b); } int diff = bi-ai+1; int db = DB[diff]; int s = 1 << db; int c = min(D1[db][ai], D1[db][bi-s+1])._2; return depth2[a] + depth2[b] - 2*depth2[c]; } void update1(int a, int add) { C[a] += add; int u = a; int uid; distSum += tsum[u] * add; while(1) { if(u != T.par[u]._1) { // get id before update uid = T.par[u]._2; u = T.par[u]._1; } else break; LL d = getDepth2(u, a); distSum += C[u] * d * add; LL sum1 = tsum[u] - tval1[u][uid]._1; LL c1 = tcn[u] - tval1[u][uid]._2; distSum += (d * c1 + sum1) * add; tval1[u][uid]._1 += d * add; tval1[u][uid]._2 += add; tsum[u] += d * add; tcn[u] += add; } } int main() { cin >> N >> Q; EL.resize(N-1); FOR(i,1,N) { cint3(a,b,c); --a; --b; E[a].PB(PII(b,c)); E[b].PB(PII(a,c)); EL[i-1] = PII(a,b); } FOR(q,0,Q) { cint1(K); FOR(i,0,K) { cint1(a); --a; B[i] = a; } sort(B,B+K); int c = 1; FOR(i,1,K) c += B[i-1] != B[i]; A[q].resize(c); int j = 0; FOR(i,0,c) { int k = j; while(k < K && B[j] == B[k]) ++k; A[q][i] = PII(B[j], k-j); j = k; } } T = CentroidDecom(0, N-1, EL); calc1(); // FOR(i,0,N) FOR(j,0,N) printf("%d %d : %d\n", i+1, j+1, getDepth2(i,j)); MSET(C,0); FOR(i,0,N) tval1[i].resize(T.cde[i].size(),PLI(0,0)); FOR(q,0,Q) { for(PII p: A[q]) update1(p._1, p._2); cout << distSum << nl; for(PII p: A[q]) update1(p._1, -p._2); } return 0; }