#define _USE_MATH_DEFINES #include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define MT make_tuple #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)<; using vi = vector; using vll = vector; class HLDecomposition { int cur = 0; void bfs(const vector > &G) { queue > que; vector order; que.push(make_tuple(0, -1, 0)); while (!que.empty()) { int u, pre, d; tie(u, pre, d) = que.front(); que.pop(); parent[u] = pre; depth[u] = d; order.push_back(u); for (int v : G[u])if (v != pre) { que.push(make_tuple(v, u, d + 1)); } } reverse(order.begin(), order.end()); for (int u : order) { sub[u] = 1; for (int v : G[u])if (v != parent[u])sub[u] += sub[v]; } } void dfs_stk(const vector > & G) { stack > stk; stk.push(make_pair(0, 0)); while (!stk.empty()) { int u, h, pre; tie(u, h) = stk.top(); stk.pop(); head[u] = h; id[u] = cur++; pre = parent[u]; int heavy = -1, maxi = 0; for (int v : G[u]) { if (v != pre && maxi < sub[v]) { maxi = sub[v]; heavy = v; } } for (int v : G[u]) { if (v != pre && v != heavy) { stk.push(make_pair(v, v)); } } if (heavy != -1)stk.push(make_pair(heavy, h)); } } public: vector parent, depth, sub, id, head; HLDecomposition(const vector > &G) { parent = depth = sub = id = head = vector(G.size()); bfs(G); dfs_stk(G); } /* パス(u, v)で通る頂点を半開区間の集合に変換する。 O(log(|V|)) */ vector > goUpToLCA(int u, int v) { vector > res; while (true) { if (head[u] == head[v]) { if (depth[u] > depth[v])swap(u, v); res.emplace_back(id[u], id[v] + 1); break; } else { if (depth[head[u]] > depth[head[v]])swap(u, v); res.emplace_back(id[head[v]], id[v] + 1); v = parent[head[v]]; } } reverse(res.begin(), res.end()); return res; } int getLCA(int u, int v) { while (true) { if (head[u] == head[v]) { if (depth[u] > depth[v])swap(u, v); break; } else { if (depth[head[u]] > depth[head[v]])swap(u, v); v = parent[head[v]]; } } return u; } }; void solve() { int N; cin >> N; vi U(N-1), V(N-1), W(N-1); vector G(N); rep(i, N - 1) { cin >> U[i] >> V[i] >> W[i]; G[U[i]].push_back(V[i]); G[V[i]].push_back(U[i]); } HLDecomposition hld(G); vll sm(N + 1); rep(i, N - 1) { if (hld.depth[V[i]] < hld.depth[U[i]]) { swap(U[i], V[i]); } sm[hld.id[V[i]] + 1] = W[i]; } rep(i, N)sm[i + 1] += sm[i]; int Q; cin >> Q; vector S; rep(ITER, Q) { S.clear(); int K; cin >> K; vi X(K); rep(i, K) { cin >> X[i]; } FOR(i, 1, K) { auto ps = hld.goUpToLCA(X[0], X[i]); S.insert(S.end(), all(ps)); } sort(all(S)); S.emplace_back(N + 1, N + 1); ll ans = 0; int l = -1, r = -1; rep(i, sz(S)) { if (S[i].first <= r) { smax(r, S[i].second); } else { if (i > 0) { ans += sm[r] - sm[l]; } tie(l, r) = S[i]; } } cout << ans << endl; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); solve(); return 0; }