#include <bits/stdc++.h> #define clr(x) memset((x), 0, sizeof((x))) #define all(x) (x).begin(), (x).end() #define pb push_back #define mp std::make_pair #define x first #define y second typedef std::pair<long long, long long> PII; typedef int64_t ll; typedef std::pair<ll, ll> PLL; typedef long double ld; typedef std::pair<ld, ld> PLD; typedef std::pair<double, double> PDD; using namespace std; int nxt() { int a; scanf("%d", &a); return a; } const int N = 100000; long long ans[N]; vector<PII> g[N]; int n, t; struct Data { ll delta; map<int, PII> m; void addDelta(ll val) { delta += val; } int size() { return (int)m.size(); } void addElement(int id, PII v) { long long ss = v.second - v.first * delta; if (m.count(id)) { PII w = m[id]; ans[id] += v.second * w.first + (w.second + w.first * delta) * v.first; } m[id].first += v.first; m[id].second += ss; } }; Data * merge(Data *l, Data *r) { if (l->size() < r->size()) { swap(l, r); } for (auto q : r->m) { int id = q.first; PII w = q.second; l->addElement(id, mp(w.first, w.second + w.first * (r->delta))); } delete r; return l; } vector<int> ids[N]; Data *dp[N]; void dfs(int v, int p = -1) { dp[v] = new Data(); dp[v]->delta = 0; dp[v]->m.clear(); for (int id : ids[v]) { dp[v]->addElement(id, mp(1, 0ll)); } for (PII pa : g[v]) { int to = (int)pa.first; ll len = pa.second; if (to == p) continue; dfs(to, v); dp[to]->addDelta(len); dp[v] = merge(dp[v], dp[to]); } } void solve() { n = nxt(); t = nxt(); for (int i = 0; i + 1 < n; ++i) { int a = nxt() - 1; int b = nxt() - 1; int c = nxt(); g[a].pb(mp(b, c)); g[b].pb(mp(a, c)); } for (int i = 0; i < t; ++i) { int k = nxt(); for (int j = 0; j < k; ++j) { ids[nxt() - 1].pb(i); } } dfs(0, -1); for (int i = 0; i < t; ++i) { cout << ans[i] << "\n"; } } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); double cl0 = clock(); #endif solve(); #ifdef LOCAL cerr << "time: " << (clock() - cl0) / CLOCKS_PER_SEC << endl; #endif }