#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; scanf("%d %d %lld", &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(); vector d(n); auto dfs = [&](auto dfs, int pos, int pre) -> void { for (int nxt : g_[pos]) { if (nxt == pre) continue; d[nxt] = d[pos] + w[P(pos, nxt)]; dfs(dfs, nxt, pos); } return; }; dfs(dfs, 0, -1); auto dist = [&](int u, int v) -> ll { return d[u] + d[v] - d[g.get(u, v)] * 2; }; int q; cin >> q; vector x; while (q--) { int k; scanf("%d", &k); x.resize(k); rep(i, k) scanf("%d", &x[i]); sort(all(x), [&](int u, int v) { return g.id[u] < g.id[v]; }); x.push_back(x[0]); // cout << x << '\n'; ll ans = 0; rep(i, sz(x) - 1) { ans += dist(x[i], x[i + 1]); } ans /= 2; printf("%lld\n", ans); } }