#include using namespace std; #define ll long long #define ull unsigned long long #define db double #define pii pair #define pli pair #define pil pair #define pll pair #define ti3 tuple #define int128 __int128_t #define pii128 pair const int inf = 1 << 30; const ll linf = 1e18; const db EPS = 1e-10; const db pi = acos(-1); template bool chmin(T& x, T y){ if(x > y) { x = y; return true; } else return false; } template bool chmax(T& x, T y){ if(x < y) { x = y; return true; } else return false; } // overload macro #define CAT( A, B ) A ## B #define SELECT( NAME, NUM ) CAT( NAME, NUM ) #define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT #define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 ) #define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__) // rep(overload) #define rep( ... ) VA_SELECT(rep, __VA_ARGS__) #define rep2(i, n) for (int i = 0; i < int(n); i++) #define rep3(i, a, b) for (int i = a; i < int(b); i++) #define rep4(i, a, b, c) for (int i = a; i < int(b); i += c) // repll(overload) #define repll( ... ) VA_SELECT(repll, __VA_ARGS__) #define repll2(i, n) for (ll i = 0; i < (ll)(n); i++) #define repll3(i, a, b) for (ll i = a; i < (ll)(b); i++) #define repll4(i, a, b, c) for (ll i = a; i < (ll)(b); i += c) // rrep(overload) #define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__) #define rrep2(i, n) for (int i = n - 1; i >= 0; i--) #define rrep3(i, a, b) for (int i = b - 1; i >= a; i--) #define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c) // rrepll(overload) #define rrepll( ... ) VA_SELECT(rrepll, __VA_ARGS__) #define rrepll2(i, n) for (ll i = (ll)(n) - 1; i >= 0ll; i--) #define rrepll3(i, a, b) for (ll i = b - 1; i >= (ll)(a); i--) #define rrepll4(i, a, b, c) for (ll i = b - 1; i >= (ll)(a); i -= c) // for_earh #define fore(e, v) for (auto&& e : v) // vector #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() struct undirected_graph { public: int n; vector> g; undirected_graph(int _n = 0) : n(_n), g(_n) {} void add_edge(int u, int v) { assert(0 <= u && u < n); assert(0 <= v && v < n); g[u].push_back(v); g[v].push_back(u); } }; struct LCA : undirected_graph { bool built = false; int logn = 0, s, B, logB = 0; vector euler_tour, depth, in, out, log_table, diff; vector> sparse_table; vector>> table_lookup; LCA(int _n) : undirected_graph(_n), depth(_n), in(_n), out(_n) { while ((1 << logn) <= 2 * n - 1) logn++; s = max(1, logn / 2); B = (2 * n - 2) / s + 1; while ((1 << logB) <= B) logB++; diff = vector(B, 0); log_table = vector(B, 0); sparse_table = vector(B, vector(logB, -1)); table_lookup = vector(1 << (s - 1), vector(s, vector(s, -1))); // table_loopupの構築 for (int i = 0; i < 1 << (s - 1); i++) { for (int l = 0; l < s; l++) { int ans = l, mn = 0, val = 0; for (int r = l; r < s; r++) { table_lookup[i][l][r] = ans; val += ((i >> r & 1) ? 1 : -1); if (val < mn) { mn = val; ans = r + 1; } } } } } void dfs(int v, int p) { in[v] = euler_tour.size(); euler_tour.emplace_back(v); for (auto&& u : g[v]) { if (u == p) continue; depth[u] = depth[v] + 1; dfs(u, v); euler_tour.emplace_back(v); } out[v] = euler_tour.size() - 1; } int get_min(const int& u, const int& v) { if (u == -1) return v; else if (v == -1) return u; else return depth[u] < depth[v] ? u : v; } void build() { built = true; dfs(0, -1); // table_lookup用の配列 for (int i = 0; i < 2 * n - 2; i++) { if (i / s != (i + 1) / s) continue; if (depth[euler_tour[i]] < depth[euler_tour[i + 1]]) { diff[i / s] |= 1 << (i % s); } } // sparse tableの構築 for (int i = 0; i < 2 * n - 1; i++) { int b = i / s; sparse_table[b][0] = get_min(sparse_table[b][0], euler_tour[i]); } for (int j = 1; j < logB; j++) { for (int i = 1 << j; i < min(1 << (j + 1), B); i++) { log_table[i] = j; } for (int i = 0; i < B; i++) { if (i + (1 << (j - 1)) >= B) break; int v1 = sparse_table[i][j - 1]; int v2 = sparse_table[i + (1 << (j - 1))][j - 1]; sparse_table[i][j] = get_min(sparse_table[i][j - 1], sparse_table[i + (1 << (j - 1))][j - 1]); } } } int get_lca(int u, int v) { assert(built); if (in[u] > in[v]) swap(u, v); int ret = 0; int bu = in[u] / s, bv = in[v] / s; if (bu == bv) { ret = euler_tour[bu * s + table_lookup[diff[bu]][in[u] % s][in[v] % s]]; } else { ret = get_min(euler_tour[bu * s + table_lookup[diff[bu]][in[u] % s][s - 1]], euler_tour[bv * s + table_lookup[diff[bv]][0][in[v] % s]]); if (bv - 1 - bu > 0) { int len = bv - 1 - bu; ret = get_min(ret, sparse_table[bu + 1][log_table[len]]); ret = get_min(ret, sparse_table[bv - (1 << log_table[len])][log_table[len]]); } } return ret; } }; struct auxiliary_tree : LCA { vector used; auxiliary_tree(int _n) : LCA(_n), used(_n) {} void build() { LCA::build(); } pair>, vector> get_at(vector v) { sort(v.begin(), v.end(), [&](int a, int b) { return in[a] < in[b]; }); for (auto u : v) used[u] = true; for (int i = 1; i < (int)v.size(); i++) { int lca = get_lca(v[i - 1], v[i]); if (!used[lca]) { used[lca] = true; v.emplace_back(lca); } } sort(v.begin(), v.end(), [&](int a, int b) { return in[a] < in[b]; }); vector> retg(v.size()); stack rem; for (int i = 0; i < (int)v.size(); i++) { used[v[i]] = false; while (!rem.empty() && out[v[rem.top()]] < in[v[i]]) rem.pop(); if (!rem.empty()) { int a = rem.top(), b = i; retg[a].push_back(b); retg[b].push_back(a); } rem.push(i); } return {retg, v}; } }; int N, u, v, w, Q; vector G[100010]; ll len[100010]; void dfs(int v, int p) { for (auto&& [u, w] : G[v]) { if (u == p) continue; len[u] = len[v] + w; dfs(u, v); } } int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); cin >> N; auxiliary_tree at(N); rep (i, N - 1) { cin >> u >> v >> w; at.add_edge(u, v); G[u].push_back({v, w}); G[v].push_back({u, w}); } at.build(); dfs(0, -1); cin >> Q; rep (i, Q) { int k; cin >> k; vector vs(k); rep(j, k) cin >> vs[j]; auto [g, label] = at.get_at(vs); ll ans = 0; rep (i, g.size()) { for (auto&& u : g[i]) { if (i < u) continue; ans += abs(len[label[u]] - len[label[i]]); } } cout << ans << '\n'; } }