#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()) using namespace std; using ll = long long; 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; } #pragma region LowestCommonAncestor struct StaticRMQ { public: void init(const std::vector>& _v) { _n = int(_v.size()), d.resize(_n), ceil_log2.resize(_n + 1); ceil_log2[0] = 0; ceil_log2[1] = 0; for (int i = 2; i <= _n; i++) ceil_log2[i] = ceil_log2[i >> 1] + 1; for (int i = 0; i < _n; i++) { d[i].resize(ceil_log2[_n] + 1); d[i][0] = _v[i]; } for (int b = 0; b < ceil_log2[_n]; b++) { for (int i = 0; i < _n; i++) { if (i + (1 << (b + 1)) > _n) break; d[i][b + 1] = std::min(d[i][b], d[i + (1 << b)][b]); } } } std::pair prod(int l, int r) { if (!(l < r)) return PINF; int b = ceil_log2[r - l]; return std::min(d[l][b], d[r - (1 << b)][b]); } private: int _n; std::vector>> d; std::vector ceil_log2; const std::pair PINF = {1 << 30, 1 << 30}; }; struct PlusMinusOneRMQ { public: void init(const std::vector& _v) { _n = int(_v.size()); v = _v; s = std::max(1, int(std::log2(_n) / 2)); B = (_n + s - 1) / s; std::vector> _spt(B); pattern.resize(B); for (int i = 0; i < _n; i += s) { int min_j = i; int bit = 0; for (int j = i; j < std::min(_n, i + s); j++) { if (v[j] < v[min_j]) min_j = j; if (j + 1 < std::min(_n, i + s) && v[j] < v[j + 1]) bit |= 1 << (j - i); } _spt[i / s] = {v[min_j], min_j}; pattern[i / s] = bit; } sparse_table.init(_spt); lookup_table.resize(1 << (s - 1)); for (int bit = 0; bit < (1 << (s - 1)); bit++) { lookup_table[bit].resize(s + 1); for (int l = 0; l <= s; l++) { lookup_table[bit][l].resize(s + 1, INF); int min_ = 0; int min_i = l; int sum = 0; for (int r = l + 1; r <= s; r++) { lookup_table[bit][l][r] = min_i; sum += bit >> (r - 1) & 1 ? 1 : -1; if (sum < min_) { min_ = sum; min_i = r; } } } } } int prod(int l, int r) { int m1 = (l + s - 1) / s; int m2 = r / s; int l1 = s * m1; int r1 = s * m2; if (m2 < m1) { return lookup_table[pattern[m2]][l - r1][r - r1] + r1; } int ret = INF; if (m1 > 0) { ret = argmin( ret, lookup_table[pattern[m1 - 1]][s - (l1 - l)][s] + l1 - s); } ret = argmin(ret, sparse_table.prod(m1, m2).second); if (m2 < B) { ret = argmin(ret, lookup_table[pattern[m2]][0][r - r1] + r1); } return ret; } private: int _n; int s, B; StaticRMQ sparse_table; std::vector>> lookup_table; std::vector pattern, v; const int INF = 1 << 30; int argmin(int i, int j) { if (i >= INF || j >= INF || v[i] == v[j]) return std::min(i, j); return v[i] < v[j] ? i : j; } }; struct LowestCommonAncestor { public: LowestCommonAncestor() { } LowestCommonAncestor(int n, int root = 0) : _n(n), _root(root), g(n), id(n), vs(2 * n - 1), dep(2 * n - 1) { } void add_edge(int from, int to) { assert(0 <= from && from < _n); assert(0 <= to && to < _n); g[from].push_back(to); g[to].push_back(from); } void build() { int k = 0; auto dfs = [&](auto dfs, int pos, int pre, int d) -> void { id[pos] = k; vs[k] = pos; dep[k++] = d; for (int nxt : g[pos]) { if (nxt == pre) continue; dfs(dfs, nxt, pos, d + 1); vs[k] = pos; dep[k++] = d; } }; dfs(dfs, _root, -1, 0); rmq.init(dep); } int get(int u, int v) { int l = std::min(id[u], id[v]); int r = std::max(id[u], id[v]) + 1; return vs[rmq.prod(l, r)]; } int get(int u, int v, int r) { return get(r, u) ^ get(u, v) ^ get(v, r); } int depth(int u) { return dep[id[u]]; } int dist(int u, int v) { return depth(u) + depth(v) - 2 * depth(get(u, v)); } // private: int _n, _root; std::vector> g; std::vector id, vs, dep; PlusMinusOneRMQ rmq; }; #pragma endregion int main() { int n; cin >> n; LowestCommonAncestor g(n); vector> g_(n); using P = pair; map w; rep(_, n - 1) { int u, v; ll _w; cin >> u >> v >> _w; g.add_edge(u, v); g_[u].push_back(v); g_[v].push_back(u); w[P(u, v)] = _w; w[P(v, u)] = _w; } g.build(); auto compress = [&](vector x) -> vector> { sort(all(x), [&](int u, int v) { return g.id[u] < g.id[v]; }); vector> ret(n); vector st = {x[0]}; int k = sz(x); rep(i, k - 1) { int w = g.get(x[i], x[i + 1]); if (w != x[i]) { int pre = st.back(); st.pop_back(); while (!st.empty() && g.depth(st.back()) > g.depth(w)) { ret[st.back()].push_back(pre); ret[pre].push_back(st.back()); pre = st.back(); st.pop_back(); } if (st.empty() || st.back() != w) { st.push_back(w); x.push_back(w); } ret[w].push_back(pre); ret[pre].push_back(w); } st.push_back(x[i + 1]); } while (sz(st) > 1) { int pre = st.back(); st.pop_back(); ret[st.back()].push_back(pre); ret[pre].push_back(st.back()); } return ret; }; vector d(n); auto dfs0 = [&](auto dfs0, int pos, int pre) -> void { for (int nxt : g_[pos]) { if (nxt == pre) continue; d[nxt] = d[pos] + w[P(pos, nxt)]; dfs0(dfs0, nxt, pos); } return; }; dfs0(dfs0, 0, -1); auto dist = [&](int u, int v) -> ll { return d[u] + d[v] - 2 * d[g.get(u, v)]; }; vector> gg; auto dfs = [&](auto dfs, int pos, int pre) -> ll { ll ret = 0; for (int nxt : gg[pos]) { if (nxt == pre) continue; ret += dfs(dfs, nxt, pos) + dist(pos, nxt); } return ret; }; int q; cin >> q; while (q--) { int k; cin >> k; vector x(k); cin >> x; gg = compress(x); cout << dfs(dfs, x[0], -1) << '\n'; } }