#include #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) #define yn(joken) cout<<((joken) ? "Yes" : "No")<; using vl = vector; using vs = vector; using vc = vector; using vd = vector; using vvi = vector>; using vvl = vector>; using vvd = vector>; const int INF = 1e9; const ll LINF = 1e18; template bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } template vector make_vec(size_t a) { return vector(a); } template auto make_vec(size_t a, Ts... ts) { return vector(ts...))>(a, make_vec(ts...)); } template istream& operator>>(istream& is, vector& v) { for (int i = 0; i < int(v.size()); i++) { is >> v[i]; } return is; } template ostream& operator<<(ostream& os, const vector& v) { for (int i = 0; i < int(v.size()); i++) { os << v[i]; if (i < int(v.size()) - 1) os << ' '; } return os; } template struct Edge{ int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { return to; } }; template struct Graph{ vector>> g; int es; Graph() = default; explicit Graph(int n) : g(n), es(0) {} size_t size() const{ return g.size(); } void add_directed_edge(int from, int to, T cost = 1){ g[from].emplace_back(from, to, cost, es++); } void add_edge(int from, int to, T cost = 1){ g[from].emplace_back(from, to, cost, es); g[to].emplace_back(to, from, cost, es++); } void read(int M, int padding = -1, bool weighted = false, bool directed = false){ for (int i = 0; i < M; i++){ int a, b; cin >> a >> b; a += padding; b += padding; T c = T(1); if (weighted) cin >> c; if (directed) add_directed_edge(a, b, c); else add_edge(a, b, c); } } inline vector> &operator[](const int &k){ return g[k]; } inline const vector> &operator[](const int &k) const{ return g[k]; } }; template using Edges = vector>; // HeavyLightDecomposition> HLD(g,root); などする,rootは指定しない場合0になる // size: 部分木のサイズ(元の木の頂点番号->サイズ) // depth: 深さ(元の木の頂点番号->深さ) // down: 行きがけ順(セグ木上での順番でもある) (元の木の頂点番号->行きがけ順) // up: 部分木クエリに使うやつ // nxt: ある頂点が属する連結成分の中で最も浅い頂点(元の木の頂点番号->元の木の頂点番号) // par: 親の番号(元の木の頂点番号->元の木の頂点番号) // rev: 行きがけ順から元の木の頂点番号に戻す配列 // void path_query(int u,int v,bool vertex,F f): u,vパスについての可換なクエリを処理,頂点属性ならvertexをtrueにする // void path_noncommutative_query(int u,int v,bool vertex,F f): u,vパスについての非可換なクエリを処理,頂点属性ならvertexをtrueにする // void subtree_query(int u,bool vertex,F f): uを根とする部分木についてのクエリを処理 // 上3つではいずれもラムダ式でfを渡せばよく,[l,r)についての結果をどこかにまとめる感じで書くと良い // その他,汎用的な関数がある(lca,la,dist,in_subtree,move) template struct HeavyLightDecomposition{ private: void dfs_sz(int cur){ size[cur] = 1; for (auto &dst : g[cur]){ if (dst == par[cur]){ if (g[cur].size() >= 2 && int(dst) == int(g[cur][0])) swap(g[cur][0], g[cur][1]); else continue; } depth[dst] = depth[cur] + 1; par[dst] = cur; dfs_sz(dst); size[cur] += size[dst]; if (size[dst] > size[g[cur][0]]) swap(dst, g[cur][0]); } } void dfs_hld(int cur){ down[cur] = id++; rev[down[cur]] = cur; for (auto dst : g[cur]){ if (dst == par[cur]) continue; nxt[dst] = (int(dst) == int(g[cur][0]) ? nxt[cur] : int(dst)); dfs_hld(dst); } up[cur] = id; } // [u, v) vector> ascend(int u, int v) const{ vector> res; while (nxt[u] != nxt[v]){ res.emplace_back(down[u], down[nxt[u]]); u = par[nxt[u]]; } if (u != v) res.emplace_back(down[u], down[v] + 1); return res; } // (u, v] vector> descend(int u, int v) const{ if (u == v) return {}; if (nxt[u] == nxt[v]) return {{down[u] + 1, down[v]}}; auto res = descend(u, par[nxt[v]]); res.emplace_back(down[nxt[v]], down[v]); return res; } public: G &g; int id; vector size, depth, down, up, nxt, par, rev; HeavyLightDecomposition(G &_g, int root = 0) : g(_g), id(0), size(g.size(), 0), depth(g.size(), 0), down(g.size(), -1), up(g.size(), -1), nxt(g.size(), root), par(g.size(), root), rev(g.size(), root) { dfs_sz(root); dfs_hld(root); } void build(int root){ dfs_sz(root); dfs_hld(root); } pair idx(int i) const { return make_pair(down[i], up[i]); } template void path_query(int u, int v, bool vertex, const F &f){ int l = lca(u, v); for (auto &&[a, b] : ascend(u, l)){ int s = a + 1, t = b; s > t ? f(t, s) : f(s, t); } if (vertex) f(down[l], down[l] + 1); for (auto &&[a, b] : descend(l, v)){ int s = a, t = b + 1; s > t ? f(t, s) : f(s, t); } } template void path_noncommutative_query(int u, int v, bool vertex, const F &f){ int l = lca(u, v); for (auto &&[a, b] : ascend(u, l)) f(a + 1, b); if (vertex) f(down[l], down[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(down[u] + int(!vertex), up[u]); } int lca(int a, int b){ while (nxt[a] != nxt[b]){ if (down[a] < down[b]) swap(a, b); a = par[nxt[a]]; } return depth[a] < depth[b] ? a : b; } int lca(int r, int u, int v){ return lca(r, u) ^ lca(u, v) ^ lca(v, r); } int la(int v, int k) { while(1){ int u = nxt[v]; if(down[v] - k >= down[u]) return rev[down[v] - k]; k -= down[v] - down[u] + 1; v = par[nxt[u]]; } } int dist(int a, int b) { return depth[a] + depth[b] - depth[lca(a, b)] * 2; } bool in_subtree(int a, int b) { return down[a] <= down[b] && down[b] <= up[a]; } int move(int a, int b) { assert(a != b); return (in_subtree(b, a) ? la(b, depth[b] - depth[a] - 1) : par[a]); } }; // lazy_segtree seg(int n)またはseg(vector vec)で初期化 // Sは型, S*S->Sを返す関数 S op(S a,S b)と単位元を返す関数 S e()を設定する // Fも形, f(x)を返す関数 S mapping(F f,S x)とf*gを返す関数 F composition(F f,F g)と単位元を返す関数 F id()を設定する // set(int p,S x): a[p]にxを代入する // get(int p): a[p]を取得する // prod(int l,int r): [l,r)をfoldした結果を返す // all_prod(): [0,n)をfoldした結果を返す // apply(p,f): a[p]にfを作用させる // apply(l,r,f): [l,r)にfを作用させる // max_right(int l,G g): bool g(S x)を渡すとl以降でf(prod(l,r))=trueとなる最大のrを返す // max_left: max_rightの逆 int ceil_pow2(int n){ int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } template struct lazy_segtree{ public: lazy_segtree() : lazy_segtree(0) {} lazy_segtree(int n) : lazy_segtree(vector(n, e())) {} lazy_segtree(const vector &v) : _n(int(v.size())){ log = ceil_pow2(_n); size = 1 << log; d = vector(2 * size, e()); lz = vector(size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--){ update(i); } } void set(int p, S x){ assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p){ assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S prod(int l, int r){ assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--){ if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push(r >> i); } S sml = e(), smr = e(); while (l < r){ if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } void apply(int p, F f){ assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f){ assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--){ if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r){ if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++){ if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template int max_right(int l){ return max_right(l, [](S x) { return g(x); }); } template int max_right(int l, G g){ assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do{ while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))){ while (l < size){ push(l); l = (2 * l); if (g(op(sm, d[l]))){ sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r){ return min_left(r, [](S x) { return g(x); }); } template int min_left(int r, G g){ assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do{ r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))){ while (r < size){ push(r); r = (2 * r + 1); if (g(op(d[r], sm))){ sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; vector d; vector lz; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f){ d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k){ all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; struct S{ ll used,w; }; S op(S l,S r){ return S{l.used+r.used,l.w+r.w}; } S e(){ return S{0LL,0LL}; } struct F{ ll f; }; S mapping(F f,S x){ if(f.f==-1) return x; return S{f.f*x.w,x.w}; } F composition(F f,F g){ if(f.f==-1) return g; return f; } F id(){ return F{-1LL}; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin>>N; Graph G(N); vector> E; rep(_,N-1){ ll u,v,w; cin>>u>>v>>w; G.add_edge(u,v,w); E.emplace_back(u,v,w); } HeavyLightDecomposition> HLD(G); lazy_segtree seg(N); for(auto [u,v,w]:E){ seg.set(max(HLD.down[u],HLD.down[v]),S{0,w}); } int Q; cin>>Q; rep(_,Q){ int k; cin>>k; vi V(k); cin>>V; auto f=[&](int l,int r)->void{ seg.apply(l,r,F{1}); }; for(int i=1;i