#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...)); } // build: you have to run it before you use // for_each: process [l, r] // for_each_edge: process [l, r] // distance: returns the dist (l, r) class heavy_light_decomposition { using size_type = size_t; using F = std::function; public: std::vector> g; std::vector vid, inv; private: std::vector head, sz, heavy, par, dep, type; void dfs(int root) { using P = std::pair; par[root] = -1; dep[root] = 0; std::stack

st; st.push({root, 0}); while(!st.empty()) { int v = st.top().first; int & i = st.top().second; if(i < g[v].size()) { int u = g[v][i++]; if(u == par[v]) continue; par[u] = v; dep[u] = dep[v] + 1; st.push({u, 0}); } else { st.pop(); int tmp = 0; for(auto e: g[v]) { if(e == par[v]) continue; sz[v] += sz[e]; if(tmp < sz[e]) { tmp = sz[e]; heavy[v] = e; } } } } } void bfs(int root, int c, int & k) { std::queue qu({root}); while(!qu.empty()) { int h = qu.front(); qu.pop(); for(int v = h; v != -1; v = heavy[v]) { type[v] = c; vid[v] = k++; inv[vid[v]] = v; head[v] = h; for(int e: g[v]) if(e != par[v] and e != heavy[v]) qu.push(e); } } } public: heavy_light_decomposition() {} heavy_light_decomposition(int n) : g(n), vid(n, -1), head(n), sz(n, 1), heavy(n, -1), par(n), dep(n), inv(n), type(n) {} void add_edge(int a, int b) { g[a].push_back(b); g[b].push_back(a); } void build(std::vector rs = std::vector(1, 0)) { int c = 0, k = 0; for(int r: rs) { dfs(r); bfs(r, c++, k); } } int lca(int u, int v) { while(true) { if(vid[u] > vid[v]) std::swap(u, v); if(head[u] == head[v]) return u; v = par[head[v]]; } } void for_each(int u, int v, const F & f) { while(true) { if(vid[u] > vid[v]) std::swap(u, v); f(std::max(vid[head[v]], vid[u]), vid[v]); if(head[u] != head[v]) v = par[head[v]]; else break; } } void for_each_edge(int u, int v, const F & f) { while(true) { if(vid[u] > vid[v]) std::swap(u, v); if(head[u] != head[v]) { f(vid[head[v]], vid[v]); v = par[head[v]]; } else { if(u != v) f(vid[u] + 1, vid[v]); break; } } } int distance(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } }; template class lazy_segment_tree { using value_type = Monoid; using operator_type = OperatorMonoid; using size_type = size_t; using F = std::function; using G = std::function; using H = std::function; size_type size_; size_type height_; F f; G g; H h; value_type id; operator_type id_op; std::vector data; std::vector lazy; std::vector depth; const size_type get_height(const size_type& size) const { size_type height = 1; while(1 << height < size) height++; return height; } const size_type base_size() const { return 1 << height_; } const value_type reflect(const size_type & k) { if(lazy[k] == id_op) return data[k]; int l = (k - (1 << depth[k])) * (base_size() >> depth[k]); int r = l + (base_size() >> depth[k]); return g(data[k], lazy[k], l, r); } void eval(const size_type & k) { if(lazy[k] == id_op) return; lazy[k << 1 ^ 0] = h(lazy[k << 1 ^ 0], lazy[k]); lazy[k << 1 ^ 1] = h(lazy[k << 1 ^ 1], lazy[k]); data[k] = reflect(k); lazy[k] = id_op; } void thrust(const size_type & k) { for(int i = height_; i; i--) eval(k >> i); } void recalc(size_type k) { while(k >>= 1) data[k] = f(reflect(k << 1 ^ 0), reflect(k << 1 ^ 1)); } public: lazy_segment_tree() {} lazy_segment_tree(int n, const F & f, const G & g, const H & h, const value_type & id, const operator_type & id_op) : size_(n), f(f), g(g), h(h), id(id), id_op(id_op) { height_ = get_height(size_); data.assign(base_size() << 1, id); lazy.assign(base_size() << 1, id_op); depth.assign(base_size() << 1, 0); for(int i = 0; i < height_ + 1; i++) for(int j = (1 << i); j < (1 << (i + 1)); j++) depth[j] = i; } void update(size_type a, size_type b, operator_type x) { thrust(a += base_size()); thrust(b += base_size() - 1); for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if(l & 1) lazy[l] = h(lazy[l], x), l++; if(r & 1) --r, lazy[r] = h(lazy[r], x); } recalc(a); recalc(b); } void change(size_type k, const value_type x) { thrust(k += base_size()); data[k] = x; lazy[k] = id_op; recalc(k); } const value_type fold(size_type a, size_type b) { thrust(a += base_size()); thrust(b += base_size() - 1); value_type left_value = id; value_type right_value = id; for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if(l & 1) left_value = f(left_value, reflect(l++)); if(r & 1) right_value = f(reflect(--r), right_value); } return f(left_value, right_value); } const value_type operator[](const size_type & k) { return fold(k, k + 1); } }; 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) {} void print() { printf("used = %d\n", used); printf("depth = %d\n", depth); printf("label = %d\n", label); printf("depth_all = %d\n", depth_all); printf("label_all = %d\n", 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, int l, int r) { 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; }; lazy_segment_tree A(n, f, gg, h, node(), -1); for(int i = 0; i < n; i++) { int v = hld.inv[i]; A.change(i, node(0, -1, -1, depth[v], v)); } auto kiri = [&A](int l, int r) { A.update(l, r + 1, 1); }; auto irik = [&A](int l, int r) { A.update(l, r + 1, 0); }; int q; scanf("%d", &q); while(q--) { int k = 3; scanf("%d", &k); std::vector vec(k); for(int i = 0; i < k; i++) scanf("%d", &vec[i]); if(k == 1) { printf("0\n"); continue; } i64 ans = calc(vec[0], vec[1]); int c = hld.lca(vec[0], vec[1]); hld.for_each(vec[0], vec[1], kiri); for(int i = 2; i < vec.size(); i++) { int v = vec[i]; node tmp = node(); auto tanpo = [&](int l, int r) { tmp = f(tmp, A.fold(l, r + 1)); }; hld.for_each(0, v, tanpo); if(tmp.depth == -1) { ans += calc(v, c); hld.for_each(v, c, kiri); c = hld.lca(v, c); } else { int u = tmp.label; ans += calc(u, v); hld.for_each(u, v, kiri); } } A.update(0, n, 0); printf("%lld\n", ans); } return 0; }