#include<stack> #include<cstdio> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cstring> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) #define eprintf(s...) fprintf(stderr, s) template<class T> inline void amin(T &a, const T &b) { if (b<a) a=b; } template<class T> inline void amax(T &a, const T &b) { if (a<b) a=b; } const int MAXN = 100011; const int LOGN = 17; const int MAGIC = 280; vector<pair<int, LL> > G[MAXN]; // (to, cost) int N, T; int K, X[1000011]; VI ord; int par[MAXN][LOGN]; int depth[MAXN]; LL dist[MAXN]; // <O(nlogn), O(1)> template<class T> struct IRMQ { vector<T> A; vector<vector<int> > M; IRMQ(){} IRMQ(const vector<T> &A_): A(A_) { int N = A.size(), LOGN = __lg(N)+1; M.resize(LOGN); for (int i=0; i<LOGN; i++) M[i].resize(N); for (int j=0; j<N; j++) M[0][j] = j; for (int i=0; i<LOGN-1; i++) for (int j=0; j+(1<<i)<N; j++) if (A[M[i][j+(1<<i)]] < A[M[i][j]]) M[i+1][j] = M[i][j+(1<<i)]; else M[i+1][j] = M[i][j]; } T min_v(int l, int r) { // assert(0 <= l < r <= N) return A[min_i(l, r)]; } int min_i(int l, int r) { int d = __lg(r-l); if (A[M[d][r-(1<<d)]] < A[M[d][l]]) return M[d][r-(1<<d)]; else return M[d][l]; } }; VI v; VI first, last; IRMQ<int> rmq; void LCA_init() { stack<int> s; VI iter(N); s.push(0); while (!s.empty()) { int x = s.top(); s.pop(); v.push_back(x); if (iter[x] < (int)G[x].size() && par[x][0] == G[x][iter[x]].first) iter[x]++; if (iter[x] < (int)G[x].size()) { s.push(x); s.push(G[x][iter[x]].first); iter[x]++; } } first.assign(N, -1); last.assign(N, -1); VI d(v.size()); REP (i, v.size()) { if (first[v[i]] == -1) first[v[i]] = i; last[v[i]] = i; d[i] = depth[v[i]]; } rmq = IRMQ<int>(d); } int lca(int x, int y) { if (x == y) return x; return v[ rmq.min_i(min(first[x], first[y]), max(last[x], last[y])+1) ]; } // int lca(int x, int y) { // if (depth[x] > depth[y]) swap(x, y); // int d = depth[y] - depth[x]; // for (int i=0; d >= (1<<i); i++) // if (d & (1<<i)) y = par[y][i]; // if (x == y) return x; // for (int i=LOGN; i--;) { // if (par[x][i] != par[y][i]) { // x = par[x][i]; // y = par[y][i]; // } // } // return par[x][0]; // } void init() { ord.reserve(N); ord.push_back(0); memset(par, -1, sizeof par); par[0][0] = 0; REP (i, N) { int x = ord[i]; EACH (e, G[x]) if (par[x][0] != e->first) { ord.push_back(e->first); par[e->first][0] = x; depth[e->first] = depth[x] + 1; dist[e->first] = dist[x] + e->second; } } // REP (t, LOGN-1) REP (i, N) par[i][t+1] = par[par[i][t]][t]; LCA_init(); } LL small() { LL ret = 0; REP (i, K) { ret += dist[X[i]] * (K-1LL); REP (j, i) { int z = lca(X[i], X[j]); ret -= dist[z] * 2LL; } } return ret; } int s[MAXN]; LL large() { LL ret = 0; memset(s, 0, sizeof (int) * N); REP (i, K) s[X[i]]++; REP (i_, N) { int x = ord[N-1-i_]; if (s[x] == K) break; if (s[x] == 0) continue; if (x == 0) break; s[par[x][0]] += s[x]; ret += (dist[x] - dist[par[x][0]]) * (K - s[x]) * s[x]; } return ret; } int main() { scanf("%d%d", &N, &T); REP (i, N-1) { int a, b, c; scanf("%d%d%d", &a, &b, &c); a--; b--; G[a].push_back(make_pair(b, c)); G[b].push_back(make_pair(a, c)); } init(); REP ($, T) { scanf("%d", &K); REP (i, K) scanf("%d", X+i), X[i]--; LL ans; if (K < MAGIC) ans = small(); else ans = large(); printf("%lld\n", ans); } return 0; }