#include <bits/stdc++.h> using namespace std; using ll = long long; struct SegTree { int n; vector <ll> dist, dist_x_total, lazy, total, cdist, version; vector <bool> to_clear; void Build (int at, int l, int r, vector <int>& pos, vector<ll>& d) { if (l == r) { dist[at] = d[pos[l]]; cdist[l] = d[pos[l]]; } else { int mid = (l + r) / 2; Build(at * 2, l, mid, pos, d); Build(at * 2 + 1, mid + 1, r, pos, d); dist[at] = dist[at * 2] + dist[at * 2 + 1]; } } SegTree(int n, vector <int>& pos, vector<ll>& d): n(n), dist(4 * n + 4), lazy(4 * n + 4), dist_x_total(4 * n + 4), to_clear(4 * n + 4, false), total(n), version(n), cdist(n) { Build(1, 0, n - 1, pos, d); } void Reset () { to_clear[1] = true; lazy[1] = 0; } void Push (int at, int l, int r) { if (to_clear[at]) { dist_x_total[at] = 0; to_clear[at] = false; if (l != r) { to_clear[at * 2] = true; lazy[at * 2] = 0; to_clear[at * 2 + 1] = true; lazy[at * 2 + 1] = 0; } } if (l != r) { lazy[at * 2] += lazy[at]; lazy[at * 2 + 1] += lazy[at]; } dist_x_total[at] += dist[at] * lazy[at]; lazy[at] = 0; } ll Update (int p, int v) { if (version[p] != v) { version[p] = v; total[p] = 0; } total[p]++; return cdist[p] * total[p]; } ll Update (int at, int l, int r, int x, int y) { Push(at, l, r); if (y < x) { return 0; } else if (l == x && r == y) { lazy[at]++; Push(at, l, r); // cerr << "U " << at << ' ' << l << ' ' << r << ' ' << x << ' ' << y << endl; // cerr << "-> E " << dist_x_total[at] << endl; return dist_x_total[at]; } else { int mid = (l + r) / 2; ll ret = 0; ret += Update(at * 2, l, mid, x, min(y, mid)); ret += Update(at * 2 + 1, mid + 1, r, max(x, mid + 1), y); dist_x_total[at] = dist_x_total[at * 2] + dist_x_total[at * 2 + 1]; // cerr << "U " << at << ' ' << l << ' ' << r << ' ' << x << ' ' << y << endl; // cerr << "-> E " << dist_x_total[at] << endl; return ret; } } }; struct HLD { int nodes; vector <vector<pair<int, ll>>> adj; vector <ll> dist, depth, total; vector <int> weight, pos, index, parent, grandparent; SegTree *tree; const static int root = 0; void AddEdge(int a, int b, ll d) { adj[a].emplace_back(b, d); adj[b].emplace_back(a, d); } HLD(int n): nodes(n), adj(n), dist(n), depth(n), weight(n), pos(n), parent(n), grandparent(n), index(n), total(n) { for (int i = 1; i < n; i++) { int a, b, d; cin >> a >> b >> d; AddEdge(a - 1, b - 1, d); // AddEdge(a, b, d); } Build(); int npos = 0; BuildHLD(root, -1, npos); GrandParentDFS(0, -1); tree = new SegTree(n, index, dist); } ll Update (int u, int v) { if (u == -1) { return 0; } else if (grandparent[u] == -1) { return tree->Update(pos[u], v) + Update(parent[u], v); } else { return tree->Update(1, 0, nodes - 1, pos[grandparent[u]], pos[u]) + Update(parent[grandparent[u]], v); } } void Build(int u = root, int p = -1, ll d = 0) { dist[u] = d; parent[u] = p; grandparent[u] = -1; weight[u] = 1; for (auto vd : adj[u]) { int v = vd.first; ll d = vd.second; if (v != p) { depth[v] = d + depth[u]; Build(v, u, d); weight[u] += weight[v]; } } } void BuildHLD(int u, int p, int& next_pos) { pos[u] = next_pos++; index[pos[u]] = u; sort(adj[u].begin(), adj[u].end(), [this] (const pair<int, ll>& a, const pair<int, ll>& b) { return weight[a.first] > weight[b.first]; }); // cerr << ">> idx " << u + 1 << ' ' << p + 1 << ' ' << dist[u] << ' ' // << pos[u] << ' ' << weight[u] << ' ' << depth[u] << endl; for (auto vd : adj[u]) { int v = vd.first; if (v != p) { BuildHLD(v, u, next_pos); } } } void GrandParentDFS(int u, int p) { if (p != -1) { if (pos[u] == pos[p] + 1) { grandparent[u] = grandparent[p] == -1 ? u : grandparent[p]; } } // cerr << "> G " << u + 1 << ' ' << 1 + grandparent[u] << endl; for (auto vd : adj[u]) { int v = vd.first; if (v != p) { GrandParentDFS(v, u); } } } void Reset() { tree->Reset(); } }; /* v -> u total[u]++ sum_of_depth[u] += depth[r] // sum_of_dist[u] = sum_of_depth[u] - total[u] * depth[u] ans = sum_of_dist[root] - n () */ int main(int argc, char const *argv[]) { ios::sync_with_stdio(false); int n, t; cin >> n >> t; HLD tree(n); for (int cs = 0; cs < t; cs++) { int k; cin >> k; ll ans = 0, sum_of_dist = 0; for (int i = 0; i < k; i++) { int u; cin >> u; --u; ll amt = tree.Update(u, cs); sum_of_dist += tree.depth[u]; ans += sum_of_dist + (i + 1) * tree.depth[u]; ans -= 2 * amt; // cerr << ">> " << sum_of_dist << ' ' << amt << ' ' << ans << endl; // cerr << "> " << sum_of_dist + (i + 1) * tree.depth[u] - 2 * amt << endl; } cout << ans << endl; tree.Reset(); } return 0; }