#include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> using namespace std; const int NMAX = 100010, KMAX = 1000010; int N, T, A, B, C, K, V[KMAX], Anc[20][NMAX], S[NMAX], Father[NMAX], Size[NMAX], Pos[NMAX], NowP, Level[NMAX]; vector<pair<int, int> > G[NMAX]; bool Used[NMAX]; void DFS(int Node, int Dad) { Used[Node] = 1; Anc[0][Node] = Dad; Pos[Node] = ++ NowP; Level[Node] = Level[Dad] + 1; for(int i = 0; i < G[Node].size(); ++ i) { int Vec = G[Node][i].first, Cost = G[Node][i].second; if(!Used[Vec]) { S[Vec] = S[Node] + Cost; DFS(Vec, Node); } } } void BuildAnc() { for(int i = 1; (1 << i) <= N; ++ i) for(int j = 1; j <= N; ++ j) Anc[i][j] = Anc[i - 1][Anc[i - 1][j]]; } int GetLCA(int X, int Y) { if(Level[X] <= Level[Y]) swap(X, Y); for(int i = 19; i >= 0; -- i) if(Level[X] - (1 << i) >= Level[Y]) X = Anc[i][X]; if(X == Y) return X; for(int i = 19; i >= 0; -- i) if(Anc[i][X] && Anc[i][X] != Anc[i][Y]) X = Anc[i][X], Y = Anc[i][Y]; return Anc[0][X]; } int Find(int X) { int Y, P; for(P = X; P != Father[P]; P = Father[P]); for(; X != P; ) { Y = Father[X]; Father[X] = P; X = Y; } return P; } void Merge(int X, int Y) { int RX = Find(X), RY = Find(Y); if(RX == RY) return ; if(Size[RX] >= Size[RY]) Size[RX] += Size[RY], Father[RY] = RX; else Size[RY] += Size[RX], Father[RX] = RY; } struct CompDFS { bool operator() (const int &N1, const int &N2) const { return Pos[N1] < Pos[N2]; } }; struct CompLCA { bool operator() (const pair<int, pair<int, int> > &P1, const pair<int, pair<int, int> > &P2) const { return Level[P1.first] > Level[P2.first]; } }; int main() { scanf("%i %i", &N, &T); for(int i = 1; i < N; ++ i) { scanf("%i %i %i", &A, &B, &C); G[A].push_back(make_pair(B, C)); G[B].push_back(make_pair(A, C)); } DFS(1, 0); BuildAnc(); for(int i = 1; i <= N; ++ i) Father[i] = i, Size[i] = 1; for(; T; T --) { scanf("%i", &K); for(int i = 1; i <= K; ++ i) scanf("%i", &V[i]); sort(V + 1, V + K + 1, CompDFS()); for(int i = 1; i <= K; ++ i) Size[V[i]] = 0; for(int i = 1; i <= K; ++ i) Size[V[i]] ++; vector<pair<int, pair<int, int> > > LCA; long long Ans = 0; for(int i = 1; i < K; ++ i) { int NowLCA = GetLCA(V[i], V[i + 1]); if(V[i] == V[i + 1]) continue; LCA.push_back(make_pair(NowLCA, make_pair(V[i], V[i + 1]))); } sort(LCA.begin(), LCA.end(), CompLCA()); for(int i = 1; i <= K; ++ i) Ans += 1LL * S[ V[i] ] * (K - Size[V[i]]); for(int i = 0; i < LCA.size(); ++ i) { int NowLCA = LCA[i].first, NodeA = LCA[i].second.first, NodeB = LCA[i].second.second; Ans -= 2LL * S[NowLCA] * Size[Find(NodeA)] * Size[Find(NodeB)]; Merge(NodeA, NodeB); } printf("%lld\n", Ans); for(int i = 1; i <= K; ++ i) Father[V[i]] = V[i], Size[V[i]] = 1; } }