#include #include #include #include #include #include using namespace std; void dfs(const vector>> &G, int v, int p, vector &D){ for(auto e : G[v]){ long long w; int v_; tie(w,v_) = e; if(v_ == p) continue; D[v_] = D[v]+1; dfs(G,v_,v,D); } } int main(){ int N; cin >> N; vector>> G(N); for(int i = 0; i < N-1; ++i){ int u, v, w; cin >> u >> v >> w; G[u].emplace_back(w,v); G[v].emplace_back(w,u); } vector D(N); dfs(G,0,-1,D); vector>> V(20,vector>(N)); for(int i = 0; i < N; ++i){ for(auto e : G[i]){ int v_ = e.second; if(D[i] == D[v_]+1){ V[0][i] = e; } } } // cerr << "D : "; // for(auto d : D) cerr << d << " "; // cerr << endl; for(int i = 1; i < 20; ++i){ for(int j = 0; j < N; ++j){ auto s = V[i-1][j]; auto t = V[i-1][s.second]; V[i][j] = {s.first+t.first,t.second}; } } auto solve = [&](vector X){ long long ret = 0; set S; for(auto x : X) S.insert(x); while(true){ int max_d = 0, min_d = 100; for(auto v : S){ max_d = max(max_d, D[v]); min_d = min(min_d, D[v]); } if(max_d == min_d) break; set S_; for(auto v : S){ if(D[v] < max_d){ S_.insert(v); continue; } ret += V[0][v].first; S_.insert(V[0][v].second); } S = S_; } while(S.size() > 1){ for(int k = 19; k >= 0; --k){ set S_; for(auto v : S){ S_.insert(V[k][v].second); } if(S_.size() == S.size()){ for(auto v : S){ ret += V[k][v].first; } swap(S,S_); } // if(V[k][u].second != V[k][v].second){ // ret += V[k][u].first + V[k][v].first; // u = V[k][u].second; // v = V[k][v].second; // } } set S_; for(auto v : S){ ret += V[0][v].first; S_.insert(V[0][v].second); } swap(S,S_); } return ret; }; int Q; cin >> Q; while(Q--){ int k; cin >> k; vector X(k); for(int i = 0; i < k; ++i) cin >> X[i]; // auto p = solve(X[0],X[1]); // auto q = solve(X[1],X[2]); // auto r = solve(X[2],X[0]); // auto s = solve(q.second,X[0]); // fprintf(stderr,"solve(%d,%d) = (%lld,%d)\n",X[0],X[1],p.first,p.second); // fprintf(stderr,"solve(%d,%d) = (%lld,%d)\n",X[0],X[2],r.first,r.second); // fprintf(stderr,"solve(%d,%d) = (%lld,%d)\n",X[0],q.second,s.first,s.second); // long long ans = p.first + r.first - s.first; long long ans = solve(X); cout << ans << endl; } }