#include <cstdio> #include <vector> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> using namespace std; struct Edge { int to, length; Edge(int to, int length) : to(to), length(length) {} }; struct Pair { int child, distance, count; Pair(int child, int distance, int count) : child(child), distance(distance), count(count) {} bool operator<(const Pair& other) const { return child < other.child; } }; const int N = 100000, MAXLOG = 17; vector<Edge> edges[N]; int distanceToTop[N], heights[N]; int lca[N][MAXLOG]; bool removed[N]; int sizeBelow[N], parents[N]; vector<Pair> pairs[N]; struct Tree { int verticesCount; Tree(int verticesCount) : verticesCount(verticesCount) { } void addEdge(int from, int to, int length) { edges[from].push_back(Edge(to, length)); edges[to].push_back(Edge(from, length)); } void build() { dfs(0, -1, 0, 0); } void dfs(int u, int parent, int distance, int height) { distanceToTop[u] = distance; heights[u] = height; memset(lca[u], -1, sizeof(lca[u])); lca[u][0] = parent; for (int i = 1; i < MAXLOG; i++) { int v = lca[u][i - 1]; if (v != -1) { lca[u][i] = lca[v][i - 1]; } } for (Edge e : edges[u]) { if (e.to != parent) { dfs(e.to, u, distance + e.length, height + 1); } } } int get_lca(int u, int v) { if (heights[u] < heights[v]) { swap(u, v); } if (heights[u] > heights[v]) { for (int i = MAXLOG - 1; i >= 0; i--) { int j = (1 << i); if (heights[u] - j >= heights[v]) { u = lca[u][i]; } } } if (u == v) return u; for (int i = MAXLOG - 1; i >= 0; i--) { int a = lca[u][i], b = lca[v][i]; if (a != b) { u = a; v = b; } } u = lca[u][0]; v = lca[v][0]; return u; } inline int distance(int u, int v) { int lca = get_lca(u, v); return (distanceToTop[v] - distanceToTop[lca]) + (distanceToTop[u] - distanceToTop[lca]); } }; struct CentroidTree { Tree* sourceTree; int verticesCount; CentroidTree(Tree* sourceTree) : sourceTree(sourceTree) { } void build() { verticesCount = sourceTree->verticesCount; recursiveBuild(0, -1); } void recursiveBuild(int initVertex, int parent) { buildSizes(initVertex, -1); int newCenter = getCenter(initVertex, -1, sizeBelow[initVertex]); parents[newCenter] = parent; removed[newCenter] = true; for (Edge e : edges[newCenter]) { if (!removed[e.to]) recursiveBuild(e.to, newCenter); } } int getCenter(int u, int parent, int totalSize) { int sizeUp = totalSize - sizeBelow[u]; bool isCenter = (sizeUp <= (totalSize / 2)); for (Edge e : edges[u]) { if (e.to != parent && !removed[e.to]) isCenter &= (sizeBelow[e.to] <= (totalSize / 2)); } if (isCenter) return u; for (Edge e : edges[u]) { if (e.to != parent && !removed[e.to]) { int centerBelow = getCenter(e.to, u, totalSize); if (centerBelow != -1) return centerBelow; } } return -1; } void buildSizes(int u, int parent) { sizeBelow[u] = 1; for (Edge e : edges[u]) { if (e.to != parent && !removed[e.to]) { buildSizes(e.to, u); sizeBelow[u] += sizeBelow[e.to]; } } } long long getAns(int setSize, vector<int>& set) { long long result = 0; sort(set.begin(), set.end()); int i = 0; while (i < set.size()) { int id = set[i]; int count = 0; while (i < set.size() && set[i] == id) { ++i; ++count; } int previous = -1; int original = id; while (id != -1) { int distance = sourceTree->distance(id, original); pairs[id].push_back(Pair(previous, distance, count)); previous = id; id = parents[id]; } } int before = -1; for (int id : set) { if (id == before) continue; before = id; while (id != -1) { result += getResult(pairs[id]); pairs[id].clear(); id = parents[id]; } } return result; } long long getResult(vector<Pair>& list) { if (list.size() <= 1) return 0; long long result = 0; long long totalSum = 0; int firstChild = list[0].child; bool shouldSort = false; for (Pair p : list) { if (p.child != firstChild) shouldSort = true; totalSum += p.distance * p.count; } if (shouldSort) sort(list.begin(), list.end()); int i = 0; while (i < list.size()) { long long currentSum = 0; long long currentCount = 0; int original = i; while (i < list.size() && list[i].child == list[original].child) { Pair p = list[i]; currentSum += p.distance * p.count; currentCount += p.count; ++i; } result += currentCount * (totalSum - currentSum); } return result; } }; inline int nextInt() { int n; scanf("%d", &n); return n; } int main() { ios_base::sync_with_stdio(false); int verticesCount = nextInt(); int queriesCount = nextInt(); Tree sourceTree(verticesCount); for (int i = 0; i < verticesCount - 1; i++) { int from = nextInt() - 1; int to = nextInt() - 1; int length = nextInt(); sourceTree.addEdge(from, to, length); } sourceTree.build(); CentroidTree centroidTree(&sourceTree); centroidTree.build(); vector<int> set; for (int q = 0; q < queriesCount; q++) { int setSize = nextInt(); set.resize(setSize); for (int i = 0; i < setSize; i++) { set[i] = nextInt() - 1; } printf("%lld\n", centroidTree.getAns(setSize, set)); } return 0; }