#include using namespace std; typedef long long ll; typedef pair l_l; typedef pair i_i; template inline bool chmax(T &a, T b) { if(a < b) { a = b; return true; } return false; } template inline bool chmin(T &a, T b) { if(a > b) { a = b; return true; } return false; } #define EPS (1e-7) #define INF (1e9) #define PI (acos(-1)) //const ll mod = 1000000007; typedef vector> Graph; template class MinOp{ public: T operator () ( T a , T b ){ return min( a , b ); } }; // sparse table // static range semigroup query // time complexity: // OpFunc is binary operator: T x T -> T template struct SparseTable{ OpFunc op; int size; vector lg; vector > table; void init( const vector &array, OpFunc opfunc ){ int n = array.size(); op = opfunc; lg.assign( n + 1 , 0 ); for( int i = 1; i <= n; i++ ){ lg[i] = 31 - __builtin_clz( i ); } table.assign( lg[n] + 1, array ); for( int i = 1; i <= lg[n]; i++ ){ for( int j = 0; j < n; j++ ){ if( j + (1<<(i-1)) < n ){ table[i][j] = op( table[i-1][j] , table[i-1][j+(1<<(i-1))] ); } else { table[i][j] = table[i-1][j]; } } } } T query( int l , int r ){ assert( l < r ); return op( table[ lg[r-l] ][l], table[ lg[r-l] ][r-(1< struct PMORMQ{ vector a; SparseTable,MinOp > > sparse_table; vector > > lookup_table; vector block_type; int block_size, n_block; void init( const vector &array ){ a = array; int n = a.size(); block_size = max( 1, ( 31 - __builtin_clz( n ) ) / 2 ); while( n % block_size != 0 ){ a.push_back( a.back() + 1 ); n++; } n_block = n / block_size; vector > b( n_block, make_pair( INT_MAX, INT_MAX ) ); for( int i = 0; i < n; i++ ){ b[i/block_size] = min( b[i/block_size], make_pair( a[i], i ) ); } sparse_table.init( b, MinOp >() ); block_type.assign( n_block, 0 ); for( int i = 0; i < n_block; i++ ){ int cur = 0; for( int j = 0; j < block_size-1; j++ ){ int ind = i * block_size + j; if( a[ind] < a[ind+1] ){ cur |= 1 << j; } } block_type[i] = cur; } lookup_table.assign( 1 << (block_size-1), vector >( block_size, vector( block_size+1 ) ) ); for( int i = 0; i < (1<<(block_size-1)); i++ ){ for( int j = 0; j < block_size; j++ ){ int res = 0; int cur = 0; int pos = j; for( int k = j+1; k <= block_size; k++ ){ lookup_table[i][j][k] = pos; if( i & ( 1 << (k-1) ) ){ cur++; } else { cur--; } if( res > cur ){ pos = k; res = cur; } } } } } int query( int l, int r ){ // return position assert( l < r ); int lb = l / block_size; int rb = r / block_size; if( lb == rb ){ return lb * block_size + lookup_table[ block_type[lb] ][ l % block_size ][ r % block_size ]; } int pl = lb * block_size + lookup_table[ block_type[lb] ][ l % block_size ][ block_size ]; int pr = rb * block_size + lookup_table[ block_type[rb] ][0][ r % block_size ]; int pos = pl; if( r % block_size > 0 && a[pl] > a[pr] ){ pos = pr; } if( lb + 1 == rb ){ return pos; } int sp = sparse_table.query( lb+1, rb ).second; if( a[pos] > a[sp] ){ return sp; } return pos; } }; // LCA // time complexity: struct LCA{ int n; vector > G; PMORMQ rmq; int cnt; vector depth, id, in; void init( int size ){ n = size; G.assign( n, vector( 0 ) ); } void add_edge( int a , int b ){ G[a].push_back( b ); G[b].push_back( a ); } void dfs( int x , int p , int d ){ id[cnt] = x; depth.push_back( d ); in[x] = cnt++; for( int v : G[x] ){ if( v == p ){ continue; } dfs( v , x , d+1 ); id[cnt] = x; depth.push_back( d ); cnt++; } } void precalc( int root ){ cnt = 0; depth.clear(); in.assign( n, -1 ); id.assign( 2*n-1, -1 ); dfs( root, -1, 0 ); rmq.init( depth ); } int lca( int a , int b ){ int x = in[a]; int y = in[b]; if( x > y ){ swap( x , y ); } int pos = rmq.query( x, y + 1 ); return id[pos]; } }; vector pathes[100500]; vector children[100500]; ll cost[100500], nowcost[100500]; void DFS(int now, ll nowval) { nowval += nowcost[now]; cost[now] += nowval; nowcost[now] = 0; for(int &to : children[now]) DFS(to, nowval); } void DFS2(int now, ll nowval, ll nowsum) { cost[now] += nowsum; //cerr << "DFS" << now << " " << nowcost[now] << " " << cost[now] << endl; nowval += nowcost[now]; nowsum += nowval; nowcost[now] = 0; for(int &to : children[now]) { DFS2(to, nowval, nowsum); } } ll parent[100050]; ll dep[100050]; void initialize(int now, int from) { for(auto to : pathes[now]) { if(to == from) continue; children[now].push_back(to); parent[to] = now; dep[to] = dep[now] + 1; initialize(to, now); } } int ope, a, b; ll x; vector query; const int B = 500; ll u[100050], v[100050], w[100050]; ll num[100500]; void search(int now) { for(auto to : children[now]) { search(to); num[now] += num[to]; } } LCA lca; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; lca.init(N); parent[0] = -1; Graph G(N); for(int i = 0; i <= N - 2; i++) { cin >> u[i] >> v[i] >> w[i]; G[u[i]].push_back(v[i]); G[v[i]].push_back(u[i]); pathes[u[i]].push_back(v[i]); pathes[v[i]].push_back(u[i]); } initialize(0, -1); for(int i = 0; i < N; i++) { for(auto to : children[i]) lca.add_edge(i, to); } lca.precalc(0); /* for(int i = 0; i < N; i++) { cerr << "---" << i << "---" << endl; for(auto v : children[i]) cerr << v << " "; cerr << endl; } */ for(int i = 0; i <= N - 2; i++) { if(parent[u[i]] == v[i]) swap(u[i], v[i]); nowcost[v[i]] += w[i]; } DFS(0, 0); for(int i = 0; i < N; i++) { //cerr << i << " " << cost[i] << endl; } //LCA.build(); ll Q; cin >> Q; int timer = 0; while(Q--) { //timer++; //if(timer >= 8e4) break; ll n; cin >> n; if(n <= 100) { vector v(n), u(n); for(int i = 0; i < n; i++) cin >> v[i]; ll ans = 0; ll parent = v[0]; for(int i = 0; i < n; i++) { parent = lca.lca(parent, v[i]); } for(int i = 0; i < n; i++) { int now = parent; for(int j = 0; j < i; j++) { u[j] = lca.lca(v[i], v[j]); if(lca.lca(now, u[j]) == now) now = u[j]; } ans += cost[v[i]] - cost[now]; } cout << ans << "\n"; } else { for(int i = 0; i < N; i++) num[i] = 0; int K = n; while(n--) { ll v; cin >> v; num[v]++; } search(0); ll ans = 0; for(int i = 0; i < N - 1; i++) { int nownum = min(num[u[i]], num[v[i]]); if(0 < nownum && nownum < K) ans += w[i]; } cout << ans << "\n"; } } return 0; }