#include <iostream> #include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #include <cstring> #include <string> #include <set> #include <map> #include <cmath> #include <ctime> #include <sstream> #include <fstream> #include <functional> using namespace std; #ifdef LOCAL #define eprintf(...) fprintf(stderr, __VA_ARGS__) #else #define eprintf(...) 42 #endif typedef long long ll; typedef pair<int, int> pii; #define X first #define Y second #define mp make_pair const int LOG = 18; const int N = (int)1e5 + 10; const int Q = (int)2e6 + 10; const int pow2 = (1 << 18); struct Edge { int to, cost; Edge () : to(), cost() {} Edge (int _to, int _cost) : to(_to), cost(_cost) {} }; vector <Edge> g[N]; int n; ll dist[N]; int jump[LOG][N]; int h[N]; int tin[N], tout[N]; int tme = 0; struct SegmentTree { int tree[pow2 * 2]; SegmentTree () { memset(tree, 0, sizeof(tree)); } void clear() { memset(tree, 0, sizeof(tree)); } void addVal(int pos, int val, int v, int l, int r) { if (l == r) { tree[v] += val; return; } int m = (l + r) / 2; if (pos <= m) addVal(pos, val, 2 * v, l, m); else addVal(pos, val, 2 * v + 1, m + 1, r); tree[v] = tree[2 * v] + tree[2 * v + 1]; } void addVal(int pos, int val) { addVal(pos, val, 1, 0, pow2 - 1); } int getSum(int a, int b, int v, int l, int r) { if (l >= a && r <= b) { return tree[v]; } if (l > b || r < a) return 0; int m = (l + r) / 2; return getSum(a, b, 2 * v, l, m) + getSum(a, b, 2 * v + 1, m + 1, r); } int getSum(int a, int b) { return getSum(a, b, 1, 0, pow2 - 1); } } tree; void dfs(int v, int par) { jump[0][v] = par; for (int i = 1; i < LOG; i++) jump[i][v] = jump[i - 1][jump[i - 1][v]]; tin[v] = tme++; for (auto e : g[v]) { int to = e.to; int cost = e.cost; if (to == par) continue; dist[to] = dist[v] + cost; h[to] = h[v] + 1; dfs(to, v); } tout[v] = tme - 1; } int go(int v, int d) { for (int i = 0; i < LOG; i++) { if (d & (1 << i)) v = jump[i][v]; } return v; } int getLca(int a, int b) { if (h[a] > h[b]) a = go(a, h[a] - h[b]); else b = go(b, h[b] - h[a]); if (a == b) return a; for (int i = LOG - 1; i >= 0; i--) { if (jump[i][a] != jump[i][b]) { a = jump[i][a]; b = jump[i][b]; } } return jump[0][a]; } void prepare() { dfs(0, 0); } int cntQ; int queryV[Q]; int inter[Q]; int cntI; ll ans = 0; void init() { cntI = 0; ans = 0; } void clear() { for (int i = 0; i < cntQ; i++) tree.addVal(tin[queryV[i]], -1); } bool cmp(int a, int b) { return tin[a] < tin[b]; } set <int, bool(*)(int, int)> setV(cmp); bool isParent(int p, int v) { return tin[p] <= tin[v] && tout[p] >= tout[v]; } void smartDfs(int v) { while (!setV.empty()) { int to = *setV.begin(); if (isParent(v, to)) { setV.erase(to); int downCnt = tree.getSum(tin[to], tout[to]); int upCnt = cntQ - downCnt; ll edgeLen = dist[to] - dist[v]; ans += edgeLen * downCnt * upCnt; smartDfs(to); } else break; } } void solve() { init(); scanf("%d", &cntQ); for (int i = 0; i < cntQ; i++) { scanf("%d", &queryV[i]); queryV[i]--; } for (int i = 0; i < cntQ; i++) { tree.addVal(tin[queryV[i]], 1); } sort(queryV, queryV + cntQ, [](int a, int b) { return tin[a] < tin[b];}); for (int i = 0; i < cntQ; i++) inter[cntI++] = queryV[i]; for (int i = 0; i < cntQ - 1; i++) inter[cntI++] = getLca(queryV[i], queryV[i + 1]); sort(inter, inter + cntI, [](int a, int b) { return tin[a] < tin[b];}); cntI = unique(inter, inter + cntI) - inter; for (int i = 1; i < cntI; i++) setV.insert(inter[i]); smartDfs(inter[0]); printf("%lld\n", ans); clear(); } int main() { int t; scanf("%d%d", &n, &t); for (int i = 0; i < n - 1; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); a--, b--; g[a].push_back(Edge(b, c)); g[b].push_back(Edge(a, c)); } prepare(); for (int i = 0; i < t; i++) { solve(); } return 0; }