#line 1 "test/tree/yuki_901.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/901" #line 2 "template/template.hpp" #include #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) #define all(v) v.begin(), v.end() using ll = long long; using ld = long double; using ull = unsigned long long; template bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } namespace lib { using namespace std; } // namespace lib // using namespace lib; #line 2 "tree/HeavyLightDecomposition.hpp" #line 4 "tree/HeavyLightDecomposition.hpp" namespace lib { using namespace std; struct HeavyLightDecomposition { private: void dfs_sz(int v) { for (auto &nv : g[v]) { if (nv == par[v]) continue; par[nv] = v; depth[nv] = depth[v] + 1; dfs_sz(nv); sz[v] += sz[nv]; if (sz[nv] > sz[g[v][0]] || g[v][0] == par[v]) swap(nv, g[v][0]); } } void dfs_hld(int v) { in[v] = t++; for (auto nv : g[v]) { if (nv == par[v]) continue; nxt[nv] = (nv == g[v][0] ? nxt[v] : nv); dfs_hld(nv); } out[v] = t; } // [u, v) パスの取得 (v は u の祖先) vector> ascend(int u, int v) const { vector> res; while (nxt[u] != nxt[v]) { res.emplace_back(in[u], in[nxt[u]]); u = par[nxt[u]]; } if (u != v) res.emplace_back(in[u], in[v] + 1); return res; } // (u, v] パスの取得 (u は v の祖先) vector> descend(int u, int v) const { if (u == v) return {}; if (nxt[u] == nxt[v]) return {{in[u] + 1, in[v]}}; auto res = descend(u, par[nxt[v]]); res.emplace_back(in[nxt[v]], in[v]); return res; } public: HeavyLightDecomposition(const vector> &gh, int root = 0) : n(gh.size()), g(gh), sz(n, 1), in(n), out(n), nxt(n), par(n, -1), depth(n, 0) { nxt[root] = root; dfs_sz(root); dfs_hld(root); } int idx(int u) const { return in[u]; } int lca(int u, int v) const { while (nxt[u] != nxt[v]) { if (in[u] < in[v]) swap(u, v); u = par[nxt[u]]; } return depth[u] < depth[v] ? u : v; } int distance(int u, int v) const { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } template void path_noncommutative_query(int u, int v, bool vertex, const F &f) const { int l = lca(u, v); for (auto [a, b] : ascend(u, l)) f(a + 1, b); if (vertex) f(in[l], in[l] + 1); for (auto [a, b] : descend(l, v)) f(a, b + 1); } template void subtree_query(int u, bool vertex, const F &f) { f(in[u] + int(!vertex), out[u]); } int parent(int v) { return par[v]; } std::vector> lca_based_auxiliary_tree(std::vector); private: int n, t = 0; vector> g; vector sz, in, out, nxt, par, depth; }; } // namespace lib #line 2 "tree/lca_based_auxiliary_tree.hpp" #line 4 "tree/lca_based_auxiliary_tree.hpp" namespace lib { using namespace std; vector> HeavyLightDecomposition::lca_based_auxiliary_tree( vector vs) { if (vs.empty()) return {}; sort(all(vs), [&](int u, int v) { return in[u] < in[v]; }); auto s = vs; for(int i = 1; i < int(vs.size()); i++) { s.emplace_back(lca(vs[i-1], vs[i])); } std::sort(all(s), [&](int u, int v) { return in[u] < in[v]; }); s.erase(unique(all(s)), s.end()); stack st; st.push(s[0]); int sz = s.size(); std::vector> dfs_order(sz); dfs_order[0] = {s[0], -1}; rep(i,1,sz) { int v = s[i]; while(!st.empty()) { int u = st.top(); if(in[u] <= in[v] && in[v] < out[u]) { break; } else { st.pop(); } } assert(!st.empty()); int par = st.top(); dfs_order[i] = {v, par}; st.push(v); } return dfs_order; } } // namespace lib #line 6 "test/tree/yuki_901.test.cpp" using namespace lib; int main() { int n; std::cin >> n; std::vector g(n, std::vector()); std::vector> edges(n - 1); for (auto &[u, v, w] : edges) { std::cin >> u >> v >> w; g[u].emplace_back(v); g[v].emplace_back(u); } HeavyLightDecomposition hld(g); std::vector sum(n + 1, 0); for (auto [u, v, w] : edges) { if (hld.parent(v) == u) std::swap(u, v); sum[hld.idx(u) + 1] += w; } rep(i, 0, n) { sum[i + 1] += sum[i]; } auto path_sum = [&](int u, int v) -> ll { ll ret = 0; auto f = [&](int l, int r) -> void { if (l > r) std::swap(l, r); ret += sum[r] - sum[l]; }; hld.path_noncommutative_query(u, v, false, f); return ret; }; int q; std::cin >> q; while (q--) { int k; std::cin >> k; std::vector vs(k); for(auto &v: vs) std::cin >> v; ll ans = 0; auto auxiliary_tree = hld.lca_based_auxiliary_tree(vs); for (auto [v, par] : auxiliary_tree) { if (par != -1) { ans += path_sum(v, par); } } std::cout << ans << '\n'; } return 0; }