#include <cstdio> #include <vector> using namespace std; typedef long long ll; struct Node; struct Edge; struct Task { ll answer; ll acccount, acclength; }; struct Node { vector<Task*> taskset; vector<Edge*> outbound; int size, maxsize, dist; int id; }; struct Edge { bool blocked; int length; Node *to; Edge *inv; }; void collectNodes(Node *root, vector<Node*> &collection) { collection.push_back(root); for (auto e : root->outbound) if (!e->blocked) { e->inv->blocked = true; collectNodes(e->to, collection); e->inv->blocked = false; } } void calcSize(Node *x) { x->size = 1; for (auto e : x->outbound) if (!e->blocked) { e->inv->blocked = true; calcSize(e->to); x->size += e->to->size; e->inv->blocked = false; } } void calcMaxChildSize(Node *x, int total_size) { x->maxsize = total_size - x->size; for (auto e : x->outbound) if (!e->blocked) { x->maxsize = max(x->maxsize, e->to->size); e->inv->blocked = true; calcMaxChildSize(e->to, total_size); e->inv->blocked = false; } } Node *findCenter(Node *root) { calcSize(root); calcMaxChildSize(root, root->size); vector<Node*> allnodes; collectNodes(root, allnodes); Node *center = NULL; for (auto x : allnodes) { if (center == NULL || center->maxsize > x->maxsize) center = x; } return center; } void calcDistance(Node *root, int dist) { root->dist = dist; for (auto e : root->outbound) if (!e->blocked) { e->inv->blocked = true; calcDistance(e->to, dist + e->length); e->inv->blocked = false; } } void divide(Node *root) { auto center = findCenter(root); vector<Node*> allnodes; collectNodes(center, allnodes); // Reset accumulative variables for (auto x : allnodes) for (auto t : x->taskset) { t->acclength = 0; t->acccount = 0; } for (auto e : center->outbound) if (!e->blocked) { auto child = e->to; vector<Node*> subtree; e->inv->blocked = true; calcDistance(child, e->length); collectNodes(child, subtree); e->inv->blocked = false; // Update answer with center = LCA for (auto x : subtree) { for (auto t : x->taskset) { t->answer += t->acclength + t->acccount * x->dist; } } // Update accumulation variables. for (auto x : subtree) { for (auto t : x->taskset) { t->acclength += x->dist; t->acccount++; } } } // Update answer with paths from center to subtree for (auto t : center->taskset) { t->answer += t->acclength; } // Remove center and recur on subproblem for (auto e : center->outbound) if (!e->blocked) { e->inv->blocked = true; divide(e->to); } } Edge *makeEdge(Node *u, Node *v, int len); void addEdge(Node *u, Node *v, int len) { auto *e1 = makeEdge(u, v, len); auto *e2 = makeEdge(v, u, len); e1->inv = e2; e2->inv = e1; } Edge *makeEdge(Node *u, Node *v, int len) { auto *e = new Edge; e->blocked = false; e->length = len; e->to = v; u->outbound.push_back(e); return e; } int main() { //freopen("t.in", "r", stdin); int N, T; scanf("%d%d", &N, &T); vector<Node*> nodes; for (int i = 0; i < N; i++) { nodes.push_back(new Node); nodes.back()->id = i; } for (int i = 0; i < N-1; i++) { int a, b, len; scanf("%d%d%d", &a, &b, &len); a--; b--; addEdge(nodes[a], nodes[b], len); } vector<Task*> tasks; while (T--) { tasks.push_back(new Task); auto t = tasks.back(); t->answer = 0; int size; scanf("%d", &size); for (int j = 0; j < size; j++) { int x; scanf("%d", &x); x--; nodes[x]->taskset.push_back(t); } } divide(nodes[0]); for (auto t : tasks) printf("%lld\n", t->answer); }