#include <iostream> #include <iomanip> #include <algorithm> #include <vector> #include <string> #include <cmath> #include <memory.h> #include <sstream> #include <stack> #include <fstream> #include <cstdio> #include <unordered_map> #include <map> #include <list> #include <stdlib.h> #include <queue> #include <set> using namespace std; /* */ class RMQ { public: vector<int> tree; RMQ() { } void build(int N) { tree = vector<int> (4*N, 1000000000); } int join(int L, int R) { return min(L, R); } int set(int i, int l, int r, int x, int val) { if (l > r) { tree[i] = 1000000000; //null value return tree[i]; } if (x > r || x < l) { return tree[i]; // old unaffected value for parent update } if (l == r) { tree[i] = val; return tree[i]; } int L = set(i*2+1, l, (l+r)/2, x, val); int R = set(i*2+2, (l+r)/2+1, r, x, val); tree[i] = join(L, R); return tree[i]; } int get(int i, int l, int r, int a, int b) { if (l >= a && r <= b) { return tree[i]; } if (l > b || r < a) { return 1000000000; } int L = get(i*2+1, l, (l+r)/2, a, b); int R = get(i*2+2, (l+r)/2+1, r, a, b); int ret = join(L, R); return ret; } }; const int NMAX = 100001; int in[NMAX]; int out[NMAX]; int tourIn[NMAX]; int inMp[NMAX]; int par[NMAX]; long long dist[NMAX]; int cnt; int N, T; vector<vector<pair<int, int> > > tr; vector<int> tour; void dfs(int i, int p, int path) { in[i] = cnt; par[i] = p; inMp[cnt] = i; dist[i] = path; cnt++; tourIn[i] = tour.size(); tour.push_back(in[i]); for (int j = 0; j < tr[i].size(); j++) { if (tr[i][j].first == p) continue; dfs(tr[i][j].first, i, path + tr[i][j].second); tour.push_back(in[i]); } tour.push_back(in[i]); out[i] = cnt; } RMQ lca; int K; vector<int> residents; // 0-indexed long long bfs() { long long r = 0; priority_queue<pair<int, int> > q; for (int i = 0; i < residents.size(); i++) { q.push(make_pair(in[residents[i]], 1)); } while (q.size() > 1) { pair<int, int> top, top2; top = q.top(); q.pop(); top2 = q.top(); int L = min(tourIn[inMp[top.first]], tourIn[inMp[top2.first]]); int R = max(tourIn[inMp[top.first]], tourIn[inMp[top2.first]]); int anc = lca.get(0, 0, tour.size()-1, L, R); r += (dist[inMp[top.first]] - dist[inMp[anc]]) * top.second * (K - top.second); if (top.first == top2.first) { q.pop(); q.push(make_pair(anc, top.second + top2.second)); } else { q.push(make_pair(anc, top.second)); } } return r; } int main() { scanf("%d %d", &N, &T); tr = vector<vector<pair<int, int> > > (N); for (int i = 1; i < N; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); a--; b--; tr[a].push_back(make_pair(b, c)); tr[b].push_back(make_pair(a, c)); } dfs(0,-1,0); lca.build(tour.size()); for (int i = 0; i < tour.size(); i++) { lca.set(0, 0, tour.size() - 1, i, tour[i]); } for (int i = 0; i < T; i++) { scanf("%d", &K); residents = vector<int>(K); for (int j = 0; j < K; j++) { scanf("%d", &residents[j]); residents[j]--; } printf("%lld\n", bfs()); } }