#include <bits/stdc++.h> using namespace std; #define rep(i, from, to) for (int i = from; i < int(to); ++i) #define trav(a, x) for (auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; struct Node { int lcaindex; int depth; vi jmp; vector<ll> di; }; const int inf = numeric_limits<int>::max(); template<class T> struct RMQ { vector<vector<T>> jmp; void init(vector<T>& V) { int N = sz(V), on = 1, depth = 1; while (on < sz(V)) on *= 2, depth++; jmp.assign(depth, vector<T>(N)); jmp[0] = V; rep(i,0,depth-1) rep(j,0,N) jmp[i+1][j] = min(jmp[i][j], jmp[i][min(N - 1, j + (1 << i))]); } T query(int a, int b) { if (b <= a) return inf; int dep = 31 - __builtin_clz(b - a); return min(jmp[dep][a], jmp[dep][b - (1 << dep)]); } }; int main() { cin.sync_with_stdio(false); int N, T; cin >> N >> T; vector<vector<pii> > ed_(N); rep(i,0,N-1) { int a, b, c; cin >> a >> b >> c; --a, --b; ed_[a].push_back({b, c}); ed_[b].push_back({a, c}); } vector<tuple<int, int, int> > q = {make_tuple(0, -1, -1000)}; vector<Node> nodes(N); vi lcal; int counter = 0; while (!q.empty()) { tuple<int, int, int> pa = q.back(); q.pop_back(); int i, par, d; tie(i, par, d) = pa; lcal.push_back(par); lcal.push_back(i); nodes[i].lcaindex = counter++; nodes[i].depth = (par == -1 ? 0 : nodes[par].depth + 1); if (par != -1) { nodes[i].jmp.push_back(par); nodes[i].di.push_back(d); for (;;) { int lind = sz(nodes[i].jmp)-1; int up = nodes[i].jmp[lind]; if (lind >= sz(nodes[up].jmp)) break; ll d = nodes[i].di[lind]; nodes[i].jmp.push_back(nodes[up].jmp[lind]); nodes[i].di.push_back(d + nodes[up].di[lind]); } } trav(pa2, ed_[i]) if (pa2.first != par) { q.emplace_back(pa2.first, i, pa2.second); } } // rep(i,0,2*N) cerr << ' ' << lcal[i]; cerr << endl; auto dist = [&](int at, int lev) -> ll { assert(lev >= 0); ll ret = 0; for (int i = 0; lev; ++i) { if (lev & (1 << i)) { lev &= ~(1 << i); ret += nodes[at].di[i]; at = nodes[at].jmp[i]; } } return ret; }; RMQ<int> rmq; rmq.init(lcal); rep(ti,0,T) { int K; cin >> K; vi v(K), ev; rep(i,0,K) cin >> v[i], --v[i]; if (K <= 1) { cout << 0 << endl; } else { ll res = 0; vector<tuple<int, int, int> > ev; vi fronts(K), backs(K), counts(K); vector<ll> work(K); rep(i,0,K) fronts[i] = backs[i] = i, counts[i] = 1; sort(all(v), [&](int x, int y) { return nodes[x].lcaindex < nodes[y].lcaindex; }); rep(i,0,K-1) { int x = nodes[v[i]].lcaindex, y = nodes[v[i+1]].lcaindex; assert(x <= y); int lca = rmq.query(2*x+1, 2*y+2); // cerr << v[i] << ' ' << v[i+1] << " has lca " << lca << endl; ev.emplace_back(-nodes[lca].depth, i, lca); } sort(all(ev)); trav(e, ev) { int i, lca; tie(ignore, i, lca) = e; int a = fronts[i], b = i+1; int na = v[a], nb = v[b]; // cerr << "joining " << na << ' ' << nb << " through " << lca << endl; ll dist1 = dist(na, nodes[na].depth - nodes[lca].depth); ll dist2 = dist(nb, nodes[nb].depth - nodes[lca].depth); // cerr << "dists = " << dist1 << ' ' << dist2 << endl; // cerr << "counts = " << counts[a] << ' ' << counts[b] << endl; // cerr << "work = " << work[a] << ' ' << work[b] << endl; work[a] += dist1 * counts[a]; work[b] += dist2 * counts[b]; // cerr << "increase by " << counts[b] * work[a] << endl; // cerr << "increase by " << counts[a] * work[b] << endl; res += counts[b] * work[a]; res += counts[a] * work[b]; counts[a] += counts[b]; work[a] += work[b]; backs[a] = backs[b]; fronts[backs[a]] = a; v[a] = lca; } cout << res << endl; } } }