#line 1 "test.cpp" // competitive-verifier: PROBLEM https://yukicoder.me/problems/3407 #include using namespace std; #line 7 "/home/hidehic0/src/github.com/hidehic0/library_cpp/templates/alias.hpp" template using VC = std::vector; template using rpriority_queue = std::priority_queue, std::greater>; using ll = long long; using ld = long double; using pii = std::pair; using vi = VC; using vvi = VC; using vvvi = VC; using vb = VC; using vvb = VC; using vf = VC; using vvf = VC; using vpii = VC; using vvpii = VC; using si = std::set; using spii = std::set; using mii = std::map; const std::string upperlist = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const std::string lowerlist = "abcdefghijklmnopqrstuvwxyz"; #define mp make_pair #define dms << " " << constexpr int MOD998 = 998244353; #line 4 "/home/hidehic0/src/github.com/hidehic0/library_cpp/templates/macro.hpp" // 引数の長さで内容が変わるrep 参考: https://trap.jp/post/1224 #define overload4(a, b, c, d, ...) d #define _rep(i, n) for (int i = 0; i < (int)(n); i++) #define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i) #define rep(...) overload4(__VA_ARGS__, REP, _rep)(__VA_ARGS__) #define _rrep(i, n) for (int i = n - 1; i >= 0; i--) #define RREP(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); i--) #define rrep(...) overload4(__VA_ARGS__, RREP, _rrep)(__VA_ARGS__) #define all(a) (a).begin(), (a).end() template bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } template std::istream &operator>>(std::istream &is, std::pair &p) { is >> p.first >> p.second; return is; } template std::istream &operator>>(std::istream &is, std::vector &v) { for (T &in : v) is >> in; return is; } template std::ostream &operator<<(std::ostream &os, const std::vector &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 == v.size() ? "" : " "); } return os; } // pythonのprintライクな関数 参考: // https://nyaannyaan.github.io/library/template/inout.hpp inline void out() { std::cout << std::endl; } template void out(const T &t, const U &...u) { std::cout << t; if (sizeof...(u)) std::cout << sep; out(u...); } // cinの短縮関数 参考: https://nyaannyaan.github.io/library/template/inout.hpp inline void in() {} template void in(T &t, U &...u) { std::cin >> t; in(u...); } template inline T ceil_div(T a, T b) { return (a + b - 1) / b; } template inline T mod_pow(T a, T n, T mod) { T res = 1; while (n) { if (n % 2 != 0) { res *= a; res %= mod; } a *= a; a %= mod; n >>= 1; } return res; } template inline T minus_mod(T a, T b) { return ((a % b) + b) % b; } template void apply_vec(std::vector &v, T (*fn)(T)) { for (int i = 0; i < v.size(); i++) v[i] = fn(v[i]); } #line 6 "test.cpp" #line 3 "/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/auxiliary_tree.hpp" #line 2 "/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/lca.hpp" #line 4 "/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/lca.hpp" #line 7 "/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/lca.hpp" template struct LcaWithDoubling { VC> G, P; VC D; T N, K; LcaWithDoubling(VC> G, T st = 0) : G{G}, N{G.size()} { assert(N > 0); assert(st < N); K = std::bit_width((unsigned)N); P.resize(K, VC(N, -1)); D.resize(N); auto dfs = [&](const auto &self, T cur, T par, T d) -> void { P[0][cur] = par; D[cur] = d; for (auto nxt : G[cur]) { if (nxt == par) continue; self(self, nxt, cur, d + 1); } }; dfs(dfs, st, st, 0); rep(b, K - 1) rep(i, N) P[b + 1][i] = P[b][P[b][i]]; } T lca(T u, T v) { if (D[u] < D[v]) std::swap(u, v); rep(k, K) { if ((D[u] - D[v]) >> k & 1) { u = P[k][u]; } } if (u == v) { return u; } rrep(k, K) { if (P[k][u] != P[k][v]) { u = P[k][u], v = P[k][v]; } } return P[0][u]; } }; #line 5 "/home/hidehic0/src/github.com/hidehic0/library_cpp/tree/auxiliary_tree.hpp" template struct AuxiliaryTree { LcaWithDoubling lca; std::vector order; int n; AuxiliaryTree(std::vector> G) : lca{G} { n = G.size(); order.resize(n); int cnt = 0; auto dfs = [&](int cur, int par, const auto &self) -> void { order[cur] = cnt++; for (auto nxt : G[cur]) { if (nxt == par) continue; self(nxt, cur, self); } }; dfs(0, -1, dfs); } /** * @fn build * @brief AuxiliaryTreeを構築します * @param V 頂点のリスト 後で補助に使われた頂点も追加される */ T build(std::vector &V, std::vector> &G) { int m = V.size(); assert(n == G.size()); assert(m > 0); std::ranges::sort(V, [&](int a, int b) { return order[a] < order[b]; }); std::vector st = {V[0]}; for (int i = 0; i < m - 1; i++) { T w = lca.lca(V[i], V[i + 1]); if (w != V[i]) { T last = st.back(); st.pop_back(); while (!st.empty() && lca.D[w] < lca.D[st.back()]) { int tp = st.back(); st.pop_back(); G[tp].emplace_back(last); last = tp; } if (st.empty() || st.back() != w) { st.emplace_back(w), V.emplace_back(w); G[w] = {last}; } else { G[w].emplace_back(last); } } st.emplace_back(V[i + 1]); } for (int i = 0; i < st.size() - 1; i++) { G[st[i]].emplace_back(st[i + 1]); } return st[0]; } }; /** * @file tree/auxiliary_tree.hpp * @brief AuxiliaryTree * @auther hidehic0 * @date 2026-05-29 * verify: https://atcoder.jp/contests/abc340/submissions/76203724 */ #line 8 "test.cpp" int main() { ll N; in(N); vi D(N, 0); vvi VG(N); vvpii G(N); rep(_, N - 1) { ll u, v, w; in(u, v, w); G[u].emplace_back(v, w), G[v].emplace_back(u, w); VG[u].emplace_back(v), VG[v].emplace_back(u); } AuxiliaryTree AT(VG); auto dfs = [&](ll cur, ll par, ll d, const auto &self) -> void { D[cur] = d; for (auto [nxt, w] : G[cur]) { if (nxt == par) continue; self(nxt, cur, d + w, self); } }; dfs(0, -1, 0, dfs); ll Q; in(Q); vvi AG(N); while (Q--) { ll K; in(K); vi X(K); in(X); ll root = AT.build(X, AG), res = 0; auto dfs = [&](ll cur, const auto &self) -> void { for (auto nxt : AG[cur]) { res += D[nxt] - D[cur]; self(nxt, self); } }; dfs(root, dfs); out(res); for (auto x : X) AG[x].clear(); } }