// #define DEBUGGING #include using namespace std; #define endl '\n' #define ALL(V) (V).begin(), (V).end() #define ALLR(V) (V).rbegin(), (V).rend() template using V = vector; template using VV = V>; using ll = int64_t; using ull = uint64_t; using PLL = pair; template const T& var_min(const T &t) { return t; } template const T& var_max(const T &t) { return t; } template const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); } template const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); } template void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); } template void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); } template const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); } template void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); } namespace init__ { struct InitIO { InitIO() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(30); } } init_io; } #ifdef DEBUGGING // #include "../debug/debug.cpp" #include "../../debug/debug.cpp" #else #define DEBUG(...) 0 #define DEBUG_SEPARATOR_LINE 0 #endif template T make_v(T init) { return init; } template auto make_v(T init, size_t s, Tail... tail) { #define rec make_v(init, tail...) return V(s, rec); #undef rec } template struct HeavyLightDecomposition { ll root; const Graph &graph; V subtree_size, head, parent_node_idx, decomposed_id, component_id, heavy_edge_to; HeavyLightDecomposition(const Graph &graph) : root(0), graph(graph), subtree_size(graph.size()), head(graph.size()), parent_node_idx(graph.size()), decomposed_id(graph.size()), component_id(graph.size()), heavy_edge_to(graph.size()) { } ll count_size(ll cur, ll pre) { ll ret = 1; parent_node_idx[cur] = pre; ll max_size = 0, max_size_to = -1; for(ll nxt : graph[cur]) { if(nxt == pre) continue; ll res = count_size(nxt, cur); if(max_size < res) { max_size = res; max_size_to = nxt; } ret += res; } heavy_edge_to[cur] = max_size_to; return subtree_size[cur] = ret; } ll get_decomposed_id(ll node) { return node == -1 ? -1 : decomposed_id[node]; } void build_component(ll cur, ll pre, ll &decomposed_id_counter, ll &total_hl) { decomposed_id[cur] = decomposed_id_counter++; component_id[cur] = total_hl; head[cur] = (get_decomposed_id(pre) == -1 ? cur : component_id[cur] == component_id[pre] ? head[pre] : cur); if(heavy_edge_to[cur] != -1) build_component(heavy_edge_to[cur], cur, decomposed_id_counter, total_hl); for(ll nxt : graph[cur]) { if(nxt == pre || nxt == heavy_edge_to[cur]) continue; build_component(nxt, cur, decomposed_id_counter, ++total_hl); } } void decompose() { count_size(root, -1); ll decomposed_id_counter = 0; ll total_hl = 0; build_component(root, -1, decomposed_id_counter, total_hl); } // careful : when query handle edges template T query(ll n1, ll n2, const function &calc_component, T identity, const function &merge) { T lval = identity, rval = identity; T result = identity; while(true) { } return result; } void query(ll n1, ll n2, const function &calc_component) { ll identity = 0; auto merge = [&](ll a, ll b) { return 0; }; auto wrapper_calc = [&](ll a, ll b) { calc_component(a, b); return 0; }; query(n1, n2, wrapper_calc, identity, merge); } }; int main() { ll N; cin >> N; VV edges(N); map costs; for(ll i = 1; i < N; i++) { ll a, b, c; cin >> a >> b >> c; if(b < a) swap(a, b); edges[a].push_back(b); edges[b].push_back(a); costs[PLL(a, b)] = c; } HeavyLightDecomposition> hld(edges); hld.decompose(); V sum(N + 1); V nodes(N); V cost_to_parent(N); iota(ALL(nodes), 0ll); sort(ALL(nodes), [&](ll a, ll b) { return hld.decomposed_id[a] < hld.decomposed_id[b]; }); for(ll i = 0; i < N; i++) { sum[i + 1] = sum[i]; ll a = nodes[i], b = nodes[i + 1]; PLL key(min(a, b), max(a, b)); if(hld.component_id[a] == hld.component_id[b]) sum[i + 1] += costs[key]; if(a == hld.head[a]) { ll p = hld.parent_node_idx[a]; cost_to_parent[a] = costs[PLL(min(a, p), max(a, p))]; } } DEBUG(cost_to_parent); ll Q; cin >> Q; bool exist[N] = {}; DEBUG(nodes, sum, cost_to_parent); while(Q--) { ll k; cin >> k; priority_queue, function> pq([&](ll a, ll b) { return hld.decomposed_id[a] < hld.decomposed_id[b]; }); for(ll i = 0; i < k; i++) { ll e; cin >> e; pq.push(e); exist[e] = true; } ll ans = 0; DEBUG(k); while(1 < pq.size()) { ll n1 = pq.top(); pq.pop(); exist[n1] = false; ll n2 = pq.top(); DEBUG(make_tuple(n1, n2)); if(hld.component_id[n1] != hld.component_id[n2]) { ll head = hld.head[n1]; DEBUG(make_tuple(head, n1, n2, hld.decomposed_id[n1], hld.decomposed_id[n2])); ll parent = hld.parent_node_idx[head]; ll n1_id = hld.decomposed_id[n1]; ll head_id = hld.decomposed_id[head]; // DEBUG(make_tuple(head_id, n1, hld.head[n1], sum[head_id]-sum[n1], cost_to_parent[head])); ans += sum[n1_id] - sum[head_id]; ans += cost_to_parent[head]; if(parent != -1 && !exist[parent]) { DEBUG(parent); pq.push(parent); exist[parent] = true; } } else { ll id1 = hld.decomposed_id[n1]; ll id2 = hld.decomposed_id[n2]; // DEBUG(make_tuple(id1, id2)); ans += sum[id1] - sum[id2]; } } exist[pq.top()] = false; cout << ans << endl << flush; } return 0; }