#include <cstdio> #include <cstdlib> #include <algorithm> #include <queue> #include <cmath> #include <iostream> #include <set> #include <fstream> #include <string> #include <vector> using namespace std; #define FOR(i,s,e) for (int i=(s); i<(e); i++) #define FOE(i,s,e) for (int i=(s); i<=(e); i++) #define FOD(i,s,e) for (int i=(s); i>=(e); i--) #define LL long long #define eps 1e-9 #define pi acos(-1.0) #define fail {printf("Impossible\n"); return 0;} LL max(LL a,LL b){if (a>b){return a;} else {return b;}} LL min(LL a,LL b){if (a<b){return a;} else {return b;}} #define M 600001 int n, k; vector<int> nn[M], we[M]; vector<int> nz[M]; int uz[M]; int bb[M]; vector<int> L; int rep[M], fir[M], cnt, order[M], cc, lat[M], vis[M], root; LL pp[M]; int QQ[M]; int SP[300001][23]; LL res; int top, tot, WW[400001], height[400001]; set<int> Z; void build(){ int z = L.size() - 1; FOE(i, 1, z) SP[i][0] = L[i]; FOE(j, 1, 20){ FOE(i, 1, z){ SP[i][j] = min(SP[i][j - 1], (i + (1 << (j - 1)) > z? SP[i][j - 1]: SP[i + (1 << (j - 1))][j - 1])); } } } LL DFS3(int u, int p){ FOR(i, 0, nz[order[u]].size()){ int fu = rep[nz[order[u]][i]]; uz[u] += DFS3(fu, u); // printf("DFS3 %d %d\n", u, p); // printf("(%lld - %lld) * (%d - %d) * %d\n", pp[fu], pp[u], tot, uz[fu], uz[fu]); res += (LL)(pp[fu] - pp[u]) * (tot - uz[fu]) * uz[fu]; } return uz[u]; } int LCA(int a, int b){ int s1 = order[a]; int s2 = order[b]; if (s1 > s2){ int t = s2; s2 = s1; s1 = t; } s1 = fir[s1]; s2 = lat[s2]; int dist = s2 - s1 + 1; return rep[min(SP[s1][bb[dist]], SP[s2 - (1 << bb[dist]) + 1][bb[dist]])]; } void DFS(int u, int p, int hh, LL dist){ pp[u] = dist; ++cnt; ++cc; height[cc] = hh; order[u] = cc; rep[cc] = u; fir[cc] = lat[cc] = cnt; L.push_back(order[u]); FOR(i, 0, nn[u].size()) if (nn[u][i] != p){ DFS(nn[u][i], u, hh + 1, dist + (LL)we[u][i]); ++cnt; lat[order[u]] = cnt; L.push_back(order[u]); } } void push_S(int q){ // printf("TRYING TO INSERT %d\n", q); // FOE(i, 1, top) printf("%d ", WW[i]); // puts(""); while (top && WW[top] > q){ if (top == 1) { nz[q].push_back(WW[top]); // printf("BUILD %d -> %d\n", rep[q], rep[WW[top]]); } else if (WW[top - 1] > q){ nz[WW[top - 1]].push_back(WW[top]); // printf("BUILD %d -> %d\n", rep[WW[top - 1]], rep[WW[top]]); } else { nz[q].push_back(WW[top]); // printf("BUILD %d -> %d\n", rep[q], rep[WW[top]]); } top--; } if (Z.find(q) != Z.end()) return; Z.insert(q); top++; WW[top] = q; } int main(){ // freopen("out.ans", "w", stdout); scanf("%d%d", &n, &k); FOE(i, 1, n - 1){ int a, b, c; scanf("%d%d%d", &a, &b, &c); nn[a].push_back(b); we[a].push_back(c); nn[b].push_back(a); we[b].push_back(c); } L.push_back(2); cnt = 0; cc = 0; FOE(i, 1, n) vis[i] = 0; DFS(1, -1, 1, 0); build(); int w = 1; int hh = 4; int last = 1; bb[1] = 0; while (hh <= 300000){ FOE(i, last + 1, hh - 1) bb[i] = w; last = hh - 1; hh *= 2; w++; } FOE(i, 1, k){ res = 0; int t; scanf("%d", &t); FOE(j, 1, t) scanf("%d", &QQ[j]); FOE(j, 1, t) QQ[j] = order[QQ[j]]; sort(QQ + 1, QQ + t + 1); while (Z.size()) Z.erase(Z.begin()); top = 0; tot = t; root = QQ[1]; FOE(j, 1, t - 1){ uz[rep[QQ[j]]]++; int w = order[LCA(rep[QQ[j]], rep[QQ[j + 1]])]; push_S(QQ[j]); push_S(w); root = min(root, w); root = min(root, QQ[j]); } uz[rep[QQ[t]]]++; root = min(root, QQ[t]); push_S(QQ[t]); FOE(i, 1, top - 1) { // printf("BUILD %d -> %d\n", rep[WW[i]], rep[WW[i+1]]); nz[WW[i]].push_back(WW[i + 1]); } DFS3(root, -1); printf("%lld\n", res); for (set<int>::iterator it = Z.begin(); it != Z.end(); ++it){ int hype = *it; while (nz[hype].size()) nz[hype].pop_back(); uz[rep[hype]] = 0; } } return 0; }