#include <algorithm> #include <cstdio> #include <cstring> #include <map> #include <queue> #include <utility> #include <vector> typedef long long Long; const int N = 100000; const int D = 20; int dfs_count, dfn[N], pos[N], depth[N], sum[N], jump[N][D]; std::vector<std::pair<int, int>> tree[N]; void prepare(int p, int u) { pos[dfn[u] = dfs_count ++] = u; depth[u] = ~p ? depth[p] + 1 : 0; memset(jump[u], -1, sizeof(jump[u])); jump[u][0] = p; for (int i = 0; ~jump[u][i]; ++ i) { jump[u][i + 1] = jump[jump[u][i]][i]; } for (const auto &it : tree[u]) { int v = it.first; if (v != p) { sum[v] = sum[u] + it.second; prepare(u, v); } } } int lca(int a, int b) { if (depth[a] > depth[b]) { std::swap(a, b); } for (int i = D - 1; i >= 0; -- i) { if (depth[b] - depth[a] >> i & 1) { b = jump[b][i]; } } if (a == b) { return a; } for (int i = D - 1; i >= 0; -- i) { if (jump[a][i] != jump[b][i]) { a = jump[a][i]; b = jump[b][i]; } } return jump[a][0]; } typedef std::map<int, int>::iterator Iter; struct Data { Data(const Iter &it) : it(it) {} int v() const { return pos[it->first]; } Iter it; }; bool operator < (const Data &a, const Data &b) { return depth[a.v()] < depth[b.v()]; } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n - 1; ++ i) { int a, b, c; scanf("%d%d%d", &a, &b, &c); a --; b --; tree[a].push_back({b, c}); tree[b].push_back({a, c}); } dfs_count = 0; sum[0] = 0; prepare(-1, 0); while (m --) { int k; scanf("%d", &k); std::map<int, int> vertices; for (int i = 0; i < k; ++ i) { int x; scanf("%d", &x); vertices[dfn[-- x]] ++; } long long result = 0; std::priority_queue<Data> q; for (Iter it = vertices.begin(); it != vertices.end(); ++ it) { q.push(Data(it)); } while ((int)vertices.size() >= 2) { Iter it = q.top().it; q.pop(); int v = pos[it->first]; std::pair<int, int> w(0, 0); if (it != vertices.begin()) { Iter itit = it; itit --; int ww = lca(pos[itit->first], v); w = std::max(w, {depth[ww], ww}); } { Iter itit = it; itit ++; if (itit != vertices.end()) { int ww = lca(pos[itit->first], v); w = std::max(w, {depth[ww], ww}); } } int u = w.second; result += (Long)(sum[v] - sum[u]) * it->second * (k - it->second); Iter itit = vertices.find(dfn[u]); if (itit == vertices.end()) { vertices[dfn[u]] = 0; q.push(Data(itit = vertices.find(dfn[u]))); } itit->second += it->second; vertices.erase(it); } printf("%lld\n", result); } return 0; }