#include using namespace std; template < typename Element = long > class SparseTable{ public: function operation; vector> table; vector cf; SparseTable(vector& v, Element e, function operation) : operation(operation){ long isiz = v.size(); long jsiz = 0; while((1 << jsiz) <= isiz) jsiz++; table.resize(isiz, vector(jsiz, e)); for(long i = 0; i < isiz; i++)table[i][0] = v[i]; for(long j = 1; j < jsiz; j++){ for(long i = 0; i + (1 << (j - 1)) < isiz; i++){ table[i][j] = operation(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]); } } cf.resize(isiz + 1); for(long i = 2; i <= isiz; i++) cf[i] = cf[i >> 1] + 1; } Element query(long l, long r/*半開区間*/){ assert(l < r); long b = cf[r - l]; return operation(table[l][b], table[r - (1 << b)][b]); } }; class LowestCommonAncestor{ private: long N; vector visited; vector > Tree; vector > STtable; vector STcf; void make_EularTour(long vis){ EularTour.push_back(depth[vis] * N + vis); visited[vis] = true; for(auto e : Tree[vis]){ if(visited[e]) continue; depth[e] = depth[vis] + 1; make_EularTour(e); EularTour.push_back(depth[vis] * N + vis); } } void make_SparseTable(){ SparseTable st(EularTour, LONG_MAX, [](long a, long b){return min(a, b);}); STtable = st.table; STcf = st.cf; } void make_first(){ long index = 0; for(auto e : EularTour){ first_index[e % N] = min(first_index[e % N], index); index++; } } public: vector depth; vector EularTour; vector first_index; LowestCommonAncestor(vector>& tree, long root) : Tree(tree){ N = Tree.size(); visited.resize(N, false); depth.resize(N, 0); first_index.resize(N, INT_MAX); make_EularTour(root); make_SparseTable(); make_first(); } long query(long l, long r){ long ltmp = l, rtmp = r; l = min(first_index[ltmp], first_index[rtmp]); r = max(first_index[ltmp], first_index[rtmp]) + 1; long b = STcf[r - l]; return min(STtable[l][b], STtable[r - (1 << b)][b]) % N; } }; int main(){ long N; cin >> N; vector> tree(N); vector>> tree_w(N); for(long i = 0; i < N - 1; i++){ long u, v, w; cin >> u >> v >> w; tree[u].push_back(v); tree[v].push_back(u); tree_w[u].push_back({v, w}); tree_w[v].push_back({u, w}); } LowestCommonAncestor lca(tree, 0); vector depth(N, -1); vector dfs_order(N); long ord = 0; stack> dfs; dfs.push({0, 0}); while(not dfs.empty()){ auto [v, w] = dfs.top(); dfs.pop(); depth[v] = w; dfs_order[v] = ord; ord++; for(auto [v2, w2] : tree_w[v]){ if(depth[v2] != -1) continue; dfs.push({v2, w + w2}); } } long Q; cin >> Q; while(Q--){ long res = 0; long K; cin >> K; vector t(K); for(long i = 0; i < K; i++) cin >> t[i]; sort(t.begin(), t.end(), [&](auto a, auto b){return dfs_order[a] > dfs_order[b];}); for(long i = 0; i < K; i++) res += depth[t[i % K]] + depth[t[(i + 1) % K]] - 2 * depth[lca.query(t[i % K], t[(i + 1) % K])]; cout << res / 2 << '\n'; } }