#include <bits/stdc++.h> #define MAXN 100005 #define L(node) (node << 1) #define R(node) ((L(node)) + 1) using namespace std; vector< pair<int, int> > g[MAXN]; int parent[MAXN], low[MAXN], high[MAXN], depth[MAXN], cnt[MAXN]; int nodeToChain[MAXN], head[MAXN]; pair<int, int> city[1000006]; long long acc[MAXN], result; int ind; vector<int> v; vector< vector<int> > chains; void setTree(int node) { low[node] = ind; cnt[node] = 1; for (int i = 0; i < int(g[node].size()); i++) { int child = g[node][i].first; int price = g[node][i].second; if (child == parent[node]) continue; acc[child] = acc[node] + price; depth[child] = 1 + depth[node]; parent[child] = node; setTree(child); cnt[node] += cnt[child]; } high[node] = ind++; } void addNodeToChain(int node, int chain) { while (chain >= int(chains.size())) chains.push_back(v); if (chains[chain].size() == 0) head[chain] = node; nodeToChain[node] = chain; chains[chain].push_back(node); } void hld(int node) { for (int i = 0; i < int(g[node].size()); i++) { int child = g[node][i].first; if (child == parent[node]) continue; if (cnt[child] * 2 > cnt[node]) addNodeToChain(child, nodeToChain[node]); else addNodeToChain(child, chains.size()); hld(child); } } bool isParent(int node, int parent) { return low[parent] <= high[node] && high[node] <= high[parent]; } int lca(int node1, int node2) { int chain = nodeToChain[node1]; if (!isParent(node2, head[chain])) return lca(parent[head[chain]], node2); int start = -1; int end = chains[chain].size(); while (end - start > 1) { int mid = (end + start) >> 1; if (isParent(node2, chains[chain][mid]) && isParent(node1, chains[chain][mid])) start = mid; else end = mid; } return chains[chain][start]; } struct Node { int node, cnt; long long sum; Node() { node = 0; cnt = 0; sum = 0; } Node(int node_, int cnt_, long long sum_) { node = node_; cnt = cnt_; sum = sum_; } Node merge(const Node &x, int lca) { Node ret = Node(lca, cnt + x.cnt, sum + x.sum); ret.sum += x.cnt * (acc[x.node] - acc[lca]); ret.sum += cnt * (acc[node] - acc[lca]); result += (x.cnt * (acc[x.node] - acc[lca]) + x.sum) * cnt; result += (cnt * (acc[node] - acc[lca]) + sum) * x.cnt; return ret; } void print() { cout << node + 1 << " " << cnt << " " << sum << endl; } }; stack<Node> s; int main() { ios::sync_with_stdio(0); int n, q; scanf("%d%d", &n, &q); for (int i = 0; i < n - 1; i++) { int u, v, c; scanf("%d%d%d", &u, &v, &c); --u; --v; g[u].push_back(make_pair(v, c)); g[v].push_back(make_pair(u, c)); } parent[0] = -1; setTree(0); addNodeToChain(0, 0); hld(0); while (q--) { int k; scanf("%d", &k); result = 0; for (int i = 0; i < k; i++) { scanf("%d", &city[i].second); city[i].first = high[--city[i].second]; } sort(city, city + k); for (int i = 0; i < k; i++) { Node curNode = Node(city[i].second, 1, 0); while (!s.empty() && i + 1 < k) { Node leftNode = s.top(); Node rightNode = Node(city[i + 1].second, 1, 0); int left = lca(leftNode.node, curNode.node); int right = lca(curNode.node, rightNode.node); if (depth[left] >= depth[right]) { s.pop(); curNode = leftNode.merge(curNode, left); } else break; } s.push(curNode); } Node curNode = s.top(); s.pop(); while (!s.empty()) { curNode = curNode.merge(s.top(), lca(curNode.node, s.top().node)); s.pop(); } cout << result << endl; } return 0; }