#include <algorithm> #include <cassert> #include <cstdio> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> constexpr int N = 100010; std::vector<std::pair<int, int>> adj[N]; std::vector<std::pair<int, int>> new_adj[N]; int new_parent[N]; int dist[N]; int ancestor[17][N]; int depth[N]; int tin[N], tout[N], dt; int size[N]; int count[N]; void dfs(int u) { tin[u] = ++dt; depth[u] = depth[ancestor[0][u]] + 1; for (auto&& e : adj[u]) { int v = e.first; if (v != ancestor[0][u]) { ancestor[0][v] = u; dist[v] = e.second + dist[u]; dfs(v); } } tout[u] = ++dt; } int lca(int u, int v) { if (depth[u] < depth[v]) { std::swap(u, v); } for (int i = 16; i >= 0; --i) if (depth[u] - (1 << i) >= depth[v]) { u = ancestor[i][u]; } if (u == v) return u; for (int i = 16; i >= 0; --i) if (ancestor[i][u] != ancestor[i][v]) { u = ancestor[i][u]; v = ancestor[i][v]; } return ancestor[0][u]; } std::pair<long long, long long> dfs_solve(int u) { long long ret = 0; long long sum = 0; size[u] = count[u]; for (auto&& edge : new_adj[u]) { int v = edge.first; int c = edge.second; auto&& p = dfs_solve(v); ret += p.first; ret += sum * size[v] + (p.second + (long long) size[v] * c) * size[u]; sum += p.second + (long long) size[v] * c; size[u] += size[v]; } return std::make_pair(ret, sum); } int main(int argc, const char* argv[]) { // freopen("/Volumes/SSD-Xcode/Android/projects/mep/mepcpp/mepcpp/in", "r", stdin); std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; for (int i = 1; i < n; ++i) { int u, v, c; std::cin >> u >> v >> c; adj[u].emplace_back(v, c); adj[v].emplace_back(u, c); } dfs(1); for (int j = 1; 1 << j <= n; ++j) for (int i = 1; i <= n; ++i) ancestor[j][i] = ancestor[j - 1][ancestor[j - 1][i]]; while (m--) { int k; std::cin >> k; std::vector<int> verts; verts.reserve(k + k - 1); for (int i = 0; i < k; ++i) { int u; std::cin >> u; verts.push_back(u); count[u] = 0; } // long long bf = 0; // for (int u : verts) // for (int v : verts) { // int x = lca(u, v); // bf += dist[u] + dist[v] - dist[x] * 2; // } // std::cerr << "bf = " << bf / 2 << '\n'; std::sort(verts.begin(), verts.end(), [](int u, int v) { return tin[u] < tin[v]; }); for (int i = (int) verts.size() - 1; i > 0; --i) { int u = verts[i - 1]; int v = verts[i]; int x = lca(u, v); verts.push_back(x); count[x] = 0; } for (int i = 0; i < k; ++i) { count[verts[i]]++; } std::sort(verts.begin(), verts.end(), [](int u, int v) { return tin[u] < tin[v]; }); verts.erase(std::unique(verts.begin(), verts.end()), verts.end()); int new_n = (int) verts.size(); for (int i = 0; i < new_n; ++i) { int u = verts[i]; new_adj[u].clear(); } new_parent[verts[0]] = 0; for (int i = 1, u = verts[0]; i < new_n; ++i) { int v = verts[i]; while (tout[u] < tin[v]) { u = new_parent[u]; } assert(u != 0); new_adj[u].emplace_back(v, dist[v] - dist[u]); new_parent[v] = u; u = v; } auto&& ret = dfs_solve(verts[0]); std::cout << ret.first << '\n'; } }