#include <bits/stdc++.h> using namespace std; #define dbg(...) dbs(#__VA_ARGS__, __VA_ARGS__) template <class T> void dbs(string str, T t) { cerr << str << " : " << t << "\n"; } template <class T, class... S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...); } #define N 100100 #define LG 20 int parent[N], P[N][LG], level[N]; inline void init(int x, int n) { for(int i = 0; i < LG; i++) P[x][i] = -1; P[x][0] = parent[x]; for(int j = 1; (1 << j) < n; j++) if(P[x][j - 1] != -1) P[x][j] = P[P[x][j - 1]][j- 1]; } inline int lca(int x, int y) { if(level[x] < level[y]) swap(x, y); int lg = 1; while((1 << lg) <= level[x]) lg++; lg--; for(int i = lg; i >= 0; i--) { if(level[x] - (1 << i) >= level[y]) x = P[x][i]; } if(x == y) return x; for(int i = lg; i >= 0; i--) { if(P[x][i] != -1 && P[x][i] != P[y][i]) x = P[x][i], y = P[y][i]; } return parent[x]; } const int MAX_N = 100100; const int sqrtN = 1000; vector < pair <int, int> > adj[MAX_N]; int cnt[MAX_N], subCnt[MAX_N], cost[MAX_N], sum[MAX_N]; int n, q; vector <int> levelAt; vector <int> order; int tin[MAX_N]; int dfsCounter = 0; void dfsLCA(int u, int par = -1, int lev = 0, int curSum = 0) { parent[u] = par; level[u] = lev; sum[u] = curSum; tin[u] = order.size(); order.push_back(u); levelAt.push_back(lev); init(u, n); for (auto p : adj[u]) if (p.first != par) { dfsLCA(p.first, u, lev + 1, curSum + p.second); order.push_back(u); levelAt.push_back(lev); } } void calc(int u, int par = -1) { subCnt[u] = cnt[u]; for (auto p : adj[u]) if (p.first != par) { calc(p.first, u); subCnt[u] += subCnt[p.first]; } } int dp[20][MAX_N << 1]; int logVal[MAX_N << 1]; inline void initRMQ() { logVal[0] = -1; logVal[1] = 0; for(int i = 2; i < (MAX_N << 1) ; ++i) { logVal[i] = logVal[i >> 1] + 1; } for(int i = 0; i < order.size(); ++i) { dp[0][i] = i; } for(int j = 1; (1 << j) <= order.size(); j++) { for(int i = 0; i + (1 << j) <= order.size(); i++) if (levelAt[dp[j - 1][i]] < levelAt[dp[j - 1][i + (1 << (j - 1))]]) { dp[j][i] = dp[j - 1][i]; } else { dp[j][i] = dp[j - 1][i + (1 << (j - 1))]; } } } inline int getLCA(int l, int r) { if (l > r) swap(l, r); int k = logVal[r - l + 1]; if (levelAt[dp[k][l]] < levelAt[dp[k][r - (1 << k) + 1]]) return order[dp[k][l]]; else return order[dp[k][r - (1 << k) + 1]]; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> q; for (int i = 0; i < n - 1; ++i) { int u, v, w; cin >> u >> v >> w; --u, --v; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } fill(cnt, cnt + n, 0); fill(cost, cost + n, 0); fill(sum, sum + n, 0); dfsLCA(0); initRMQ(); // for (int i = 0; i < order.size(); ++i) { // dbg(i, order[i], levelAt[i]); // } for (int i = 0; i < n; ++i) { // dbg(i, parent[i], level[i], tin[i], sum[i]); for (auto j : adj[i]) { if (j.first == parent[i]) { cost[i] = j.second; break; } } } while (q--) { int k; cin >> k; vector <int> residents(k); for (int i = 0; i < k; ++i) { cin >> residents[i]; --residents[i]; } // dbg(k); long long ans = 0; if (k <= sqrtN) { for (int i = 0; i < k; ++i) { for (int j = 0; j < i; ++j) if (residents[i] != residents[j]) { int anc = getLCA(tin[residents[i]], tin[residents[j]]); // int anc = lca(residents[i], residents[j]); // dbg(residents[i], residents[j], anc); ans += sum[residents[i]] - sum[anc]; ans += sum[residents[j]] - sum[anc]; } } } else { for (int i = 0; i < k; ++i) ++cnt[residents[i]]; calc(0); for (int i = 1; i < n; ++i) { int n1 = subCnt[i]; int n2 = k - n1; ans += (long long)n1 * n2 * (long long)cost[i]; } for (int i = 0; i < k; ++i) --cnt[residents[i]]; } cout << ans << "\n"; } return 0; }