#include <stdio.h> #include <tuple> #include <algorithm> #include <vector> #include <cstring> #include <stack> using namespace std; typedef long long ll; const int MAXN = 131072; const int LOGN = 18; const int MAXK = 400; vector<pair<int, int>> tree[MAXN]; int order[MAXN]; int invorder[MAXN]; int parent[MAXN]; int o; int distP[MAXN]; int rdist[MAXN]; int r; int rmq[LOGN][2*MAXN]; int least[MAXN], largest[MAXN]; void doorder(int node) { invorder[node] = o; order[o++] = node; least[node] = r; if (r == 2*MAXN) while (1); rmq[0][r++] = invorder[node]; for (const auto &x : tree[node]) if (x.first != parent[node]) { parent[x.first] = node; distP[x.first] = x.second; doorder(x.first); if (r == 2*MAXN) while (1); rmq[0][r++] = invorder[node]; } largest[node] = r-1; } int find_lca(int a, int b) { if (a == b) return a; int l = min(least[a], least[b]); int g = max(largest[a], largest[b]); int e = 31 - __builtin_clz(g-l+1); if (e >= LOGN) while (1); int l2 = g - (1 << e) + 1; if (l2 < 0 || l2 >= r) while (1); return order[min(rmq[e][l], rmq[e][g - (1 << e) + 1])]; } int dist(int a, int b) { return rdist[a] + rdist[b] - 2*rdist[find_lca(a, b)]; } int subsum[MAXN]; int K; int query[1000010]; inline void scanint(int &x) { auto gc = getchar_unlocked; int c = gc(); x = 0; for (;(c < '0' || c > '9'); c = gc()); for (;c >= '0' && c <= '9'; c = gc()) {x = 10*x + c - '0';} } int main() { int N, T; scanint(N); scanint(T); for (int i = 0; i < N-1; i++) { int a, b, c; scanint(a); scanint(b); scanint(c); a--; b--; tree[a].emplace_back(b, c); tree[b].emplace_back(a, c); } o = 0; r = 0; parent[0] = 0; doorder(0); for (int i = 1; i < LOGN; i++) { int op = 1 << (i-1); if (op >= r) op = r-1; for (int j = 0; j < r; j++) { int op1 = rmq[i-1][j]; int op2 = rmq[i-1][op]; op++; if (op >= r) op = r - 1; rmq[i][j] = min(op1, op2); } } distP[0] = 0; for (int i = 0; i < N; i++) { int v = order[i]; rdist[v] = distP[v] + rdist[parent[v]]; } while (T--) { scanint(K); for (int k = 0; k < K; k++) { scanint(query[k]); query[k]--; } ll ans = 0; if (K < MAXK) { for (int i = 0; i < K; i++) for (int j = 0; j < i; j++) ans += dist(query[i], query[j]); } else { memset(subsum, 0, N*sizeof(int)); for (int i = 0; i < K; i++) subsum[query[i]]++; for (int i = N-1; i > 0; i--) { int v = order[i]; subsum[parent[v]] += subsum[v]; } for (int v = 1; v < N; v++) ans += (ll)distP[v] * subsum[v] * (K - subsum[v]); } printf("%lld\n", ans); } return 0; }