#include using namespace std::literals::string_literals; using i64 = long long; using std::cout; using std::endl; using std::cin; template std::vector make_v(size_t a){return std::vector(a);} template auto make_v(size_t a,Ts... ts){ return std::vector(ts...))>(a,make_v(ts...)); } class heavy_light_decomposition { public: using i32 = std::int_fast32_t; using u32 = std::uint_fast32_t; std::vector> g; std::vector edge_u, edge_v, size, et, in, out, head; std::vector parent, heavy; private: void calc_size(u32 v) { size[v] = 1; for(int id: g[v]) { int to = edge_u[id] ^ edge_v[id] ^ v; if(to == parent[v]) continue; parent[to] = v; calc_size(to); size[v] += size[to]; if(heavy[v] == -1 or size[heavy[v]] < size[to]) heavy[v] = to; } } void calc_et(u32 v) { in[v] = et.size(); et.push_back(v); if(heavy[v] != -1) { calc_et(heavy[v]); head[heavy[v]] = head[v]; } for(int id: g[v]) { int to = edge_u[id] ^ edge_v[id] ^ v; if(to == parent[v] or to == heavy[v]) continue; head[to] = to; calc_et(to); } out[v] = et.size(); } template void path(u32 x, u32 y, F& process, bool edge) const { std::vector> l, r; while(true) { if(in[x] > in[y]) { std::swap(x, y); l.swap(r); } if(head[x] == head[y]) { l.emplace_back(in[x] + !!edge, in[y] + 1); break; } l.emplace_back(in[head[y]], in[y] + 1); y = parent[head[y]]; } for(auto e: l) process(e.first, e.second); for(auto e: r) process(e.first, e.second); } template void subtree(u32 v, F& process, bool edge) const { process(in[v] + !!edge, out[v]); } public: heavy_light_decomposition() = default; heavy_light_decomposition(heavy_light_decomposition&&) = default; heavy_light_decomposition(const heavy_light_decomposition &) = default; heavy_light_decomposition(int n) : g(n), size(n), in(n), out(n), parent(n, -1), heavy(n, -1), head(n) {} void add_edge(int x, int y) { g[x].push_back(edge_u.size()); g[y].push_back(edge_v.size()); edge_u.push_back(x); edge_v.push_back(y); } void build(u32 root = 0) { calc_size(root); calc_et(root); } u32 lca(u32 x, u32 y) const { while(true) { if(in[x] > in[y]) std::swap(x, y); if(head[x] == head[y]) return x; y = parent[head[y]]; } } template void path_node(u32 x, u32 y, const F& process) const { path(x, y, process, false); } template void path_edge(u32 x, u32 y, const F& process) const { path(x, y, process, true); } template void path(u32 x, u32 y, const F& process) const { path(x, y, process, false); } template void subtree_node(u32 v, const F& process) const { subtree(v, process, false); } template void subtree_edge(u32 v, const F& process) const { subtree(v, process, true); } template void subtree(u32 v, const F& process) const { subtree(v, process, false); } u32 index_node(u32 v) const { return in[v]; }; u32 index_edge(u32 x, u32 y) const { return std::max(in[x], in[y]); }; u32 index(u32 v) const { return in[v]; }; const u32 operator[](u32 k) const { return in[k]; } }; using namespace std; template struct SegmentTree{ using F = function; using G = function; using H = function; int n,height; F f; G g; H h; T ti; E ei; vector dat; vector laz; SegmentTree(F f,G g,H h,T ti,E ei): f(f),g(g),h(h),ti(ti),ei(ei){} void init(int n_){ n=1;height=0; while(n &v){ int n_=v.size(); init(n_); for(int i=0;i>i); } inline void recalc(int k){ while(k>>=1) dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1)); } void update(int a,int b,E x){ thrust(a+=n); thrust(b+=n-1); for(int l=a,r=b+1;l>=1,r>>=1){ if(l&1) laz[l]=h(laz[l],x),l++; if(r&1) --r,laz[r]=h(laz[r],x); } recalc(a); recalc(b); } void set_val(int a,T x){ thrust(a+=n); dat[a]=x;laz[a]=ei; recalc(a); } T query(int a,int b){ thrust(a+=n); thrust(b+=n-1); T vl=ti,vr=ti; for(int l=a,r=b+1;l>=1,r>>=1) { if(l&1) vl=f(vl,reflect(l++)); if(r&1) vr=f(reflect(--r),vr); } return f(vl,vr); } }; struct node { int used; int depth; int label; int depth_all; int label_all; node() : used(1), depth(-1), label(-1), depth_all(-1), label_all(-1) {} node(int used, int depth, int label, int depth_all, int label_all) : used(used), depth(depth), label(label), depth_all(depth_all), label_all(label_all) {} }; int main() { int n; scanf("%d", &n); std::vector>> g(n); heavy_light_decomposition hld(n); for(int i = 0; i < n - 1; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); g[a].push_back({b, c}); g[b].push_back({a, c}); hld.add_edge(a, b); } hld.build(); std::vector dist(n), depth(n); auto dfs = [&](auto && dfs, int v, int par) -> void { for(auto e: g[v]) { if(e.first == par) continue; dist[e.first] = dist[v] + e.second; depth[e.first] = depth[v] + 1; dfs(dfs, e.first, v); } }; dfs(dfs, 0, -1); auto calc = [dist, &hld](int u, int v) { return dist[u] + dist[v] - 2LL * dist[hld.lca(u, v)]; }; auto f = [](node a, node b) { node ret; ret.used = 0; if(a.depth_all > b.depth_all) { ret.label_all = a.label_all; ret.depth_all = a.depth_all; } else { ret.label_all = b.label_all; ret.depth_all = b.depth_all; } int A = a.label, B = a.depth, C = b.label, D = b.depth; if(a.used) { A = a.label_all; B = a.depth_all; } if(b.used) { C = b.label_all; D = b.depth_all; } if(B > D) { ret.label = A; ret.depth = B; } else { ret.label = C; ret.depth = D; } return ret; }; auto gg = [](node a, int b) { if(b) { a.used = 1; a.depth = a.depth_all; a.label = a.label_all; } else { a.used = 0; a.depth = -1; a.label = -1; } return a; }; auto h = [](int a, int b) { return b; }; SegmentTree A(f, gg, h, node(), -1); A.init(n); for(int i = 0; i < n; i++) { int v = hld.index(i); A.set_val(i, node(0, -1, -1, depth[v], v)); } auto kiri = [&A](int l, int r) { A.update(l, r, 1); }; auto irik = [&A](int l, int r) { A.update(l, r, 0); }; int q; scanf("%d", &q); while(q--) { int k; scanf("%d", &k); std::vector vec(k); for(int i = 0; i < k; i++) scanf("%d", &vec[i]); i64 ans = 0; int c = vec.front(); for(auto v: vec) { node tmp = node(); auto tanpo = [&](int l, int r) { tmp = f(tmp, A.query(l, r)); }; hld.path(0, v, tanpo); if(tmp.depth == -1) { ans += calc(v, c); hld.path(v, c, kiri); c = hld.lca(v, c); } else { int u = tmp.label; ans += calc(u, v); hld.path(u, v, kiri); } } A.update(0, n, 0); printf("%lld\n", ans); } return 0; }