#pragma GCC optimize ("Ofast") #include using namespace std; void *wmem; char memarr[96000000]; template inline S min_L(S a,T b){ return a<=b?a:b; } template inline S max_L(S a,T b){ return a>=b?a:b; } template inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } template void sortA_L(int N, T1 a[], void *mem = wmem){ sort(a, a+N); } template void sortA_L(int N, T1 a[], T2 b[], void *mem = wmem){ int i; pair *arr; walloc1d(&arr, N, &mem); for(i=(0);i<(N);i++){ arr[i].first = a[i]; arr[i].second = b[i]; } sort(arr, arr+N); for(i=(0);i<(N);i++){ a[i] = arr[i].first; b[i] = arr[i].second; } } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } inline int rd_int(void){ int x; rd(x); return x; } inline void wt_L(char a){ putchar_unlocked(a); } inline void wt_L(long long x){ int s=0; int m=0; char f[20]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ putchar_unlocked('-'); } while(s--){ putchar_unlocked(f[s]+'0'); } } template struct LHeap{ int *hp; int *place; int size; T *val; void malloc(int N){ hp = (int*)std::malloc(N*sizeof(int)); place=(int*)std::malloc(N*sizeof(int)); val=(T*)std::malloc(N*sizeof(T)); } void walloc(int N, void **mem=&wmem){ walloc1d(&hp, N, mem); walloc1d(&place, N, mem); walloc1d(&val, N, mem); } void free(){ std::free(hp); std::free(place); std::free(val); } void init(int N){ int i; size=0; for(i=(0);i<(N);i++){ place[i]=-1; } } void up(int n){ int m; while(n){ m=(n-1)/2; if(val[hp[m]]<=val[hp[n]]){ break; } swap(hp[m],hp[n]); swap(place[hp[m]],place[hp[n]]); n=m; } } void down(int n){ int m; for(;;){ m=2*n+1; if(m>=size){ break; } if(m+1val[hp[m+1]]){ m++; } if(val[hp[m]]>=val[hp[n]]){ break; } swap(hp[m],hp[n]); swap(place[hp[m]],place[hp[n]]); n=m; } } void change(int n, T v){ T f = val[n]; val[n] = v; if(place[n]==-1){ place[n] = size; hp[size++] = n; up(place[n]); } else{ if(f < v){ down(place[n]); } else if(f > v){ up(place[n]); } } } int pop(void){ int res = hp[0]; place[res] = -1; size--; if(size){ hp[0]=hp[size]; place[hp[0]]=0; down(0); } return res; } } ; template struct fenwick{ int size; int memory; T *data; void malloc(int mem){ memory = mem; data = (T*)std::malloc(sizeof(T)*mem); } void walloc(int mem, void **workMemory=&wmem){ memory = mem; walloc1d(&data, mem, workMemory); } void free(void){ memory = 0; free(data); } void init(int N){ size = N; memset(data,0,sizeof(T)*N); } void add(int k, T val){ while(k < size){ data[k] += val; k |= k+1; } } T get(int k){ T res = 0; while(k>=0){ res += data[k]; k = (k&(k+1))-1; } return res; } T range(int a, int b){ if(b==-1){ b=size-1; } return get(b) - get(a-1); } int kth(T k){ int i=0; int j=size; int c; T v; while(i=0){ continue; } res[k]=res[i]+1; q[s+z++]=k; } } } int preorder(int res[], int root = 0, void *mem=wmem){ int i; int j; int k; int *st; int sts; int sz = 0; char *vis; walloc1d(&vis, N, &mem); walloc1d(&st, N, &mem); sts = 0; st[sts++] = root; for(i=(0);i<(N);i++){ vis[i] = 0; } vis[root] = 1; while(sts){ i = st[--sts]; res[sz++] = i; for(j=(0);j<(es[i]);j++){ k = edge[i][j]; if(vis[k]){ continue; } vis[k] = 1; st[sts++] = k; } } return sz; } } ; struct HLD{ int N; int *es; int **edge; int *group; int *groupind; int groupNum; int *groupSize; int **groupNode; int *groupUpNode; int *groupDepth; void init(graph g, void **mem = &wmem){ init(g.N, g.es, g.edge, mem); } void init(int N__, int *es__, int **edge__, void **mem = &wmem){ int i; int j; int k; int x; int y; int mx; int *q; int q_st; int q_ed; int *sz; char *vis; void *tmpmem; N = N__; es = es__; edge = edge__; walloc1d(&group, N, mem); walloc1d(&groupind, N, mem); tmpmem = *mem; walloc1d(&q, N, &tmpmem); walloc1d(&sz, N, &tmpmem); walloc1d(&vis, N, &tmpmem); for(i=(0);i<(N);i++){ vis[i] = 0; } q_st = 0; q_ed = 1; q[0] = 0; vis[0] = 1; while(q_st < q_ed){ i = q[q_st++]; for(j=(0);j<(es[i]);j++){ k = edge[i][j]; if(!vis[k]){ vis[k] = 1; q[q_ed++] = k; } } } for(i=(0);i<(N);i++){ sz[i] = 0; } for(j=N-1;j>=0;j--){ i = q[j]; sz[i] = 1; for(k=(0);k<(es[i]);k++){ sz[i] += sz[edge[i][k]]; } } for(i=(0);i<(N);i++){ group[i] = -1; } groupNum = 0; for(j=(0);j<(N);j++){ i = q[j]; if(group[i]>=0){ continue; } group[i] = groupNum++; groupind[i] = 0; for(;;){ mx = -1; for(k=(0);k<(es[i]);k++){ if(group[edge[i][k]] != -1){ continue; } if(mx==-1){ mx = k; } else if(sz[edge[i][k]] > sz[edge[i][mx]]){ mx = k; } } if(mx==-1){ break; } group[edge[i][mx]] = group[i]; groupind[edge[i][mx]] = groupind[i]+1; i = edge[i][mx]; } } walloc1d(&groupSize, groupNum, mem); walloc1d(&groupUpNode, groupNum, mem); walloc1d(&groupDepth, groupNum, mem); for(i=(0);i<(groupNum);i++){ groupSize[i] = 0; } for(i=(0);i<(N);i++){ groupSize[group[i]]++; } walloc1d(&groupNode, groupNum, mem); for(i=(0);i<(groupNum);i++){ walloc1d(&groupNode[i], groupSize[i], mem); } for(i=(0);i<(N);i++){ groupNode[group[i]][groupind[i]] = i; } for(i=(0);i<(groupNum);i++){ groupDepth[i] = -1; } groupUpNode[0] = -1; groupDepth[0] = 0; for(x=(0);x<(groupNum);x++){ for(y=(0);y<(groupSize[x]);y++){ i = groupNode[x][y]; for(j=(0);j<(es[i]);j++){ k = edge[i][j]; if(x != group[k] && groupDepth[group[k]]==-1){ groupUpNode[group[k]] = i; groupDepth[group[k]] = groupDepth[x] + 1; } } } } } int lca(int x, int y){ int x1; int y1; int x2; int y2; x1 = group[x]; x2 = groupind[x]; y1 = group[y]; y2 = groupind[y]; while(groupDepth[x1] > groupDepth[y1]){ x = groupUpNode[x1]; x1 = group[x]; x2 = groupind[x]; } while(groupDepth[x1] < groupDepth[y1]){ y = groupUpNode[y1]; y1 = group[y]; y2 = groupind[y]; } while(x1 != y1){ x = groupUpNode[x1]; x1 = group[x]; x2 = groupind[x]; y = groupUpNode[y1]; y1 = group[y]; y2 = groupind[y]; } if(x2 <= y2){ return x; } return y; } int depth(int x){ int x1; int x2; int res = 0; x1 = group[x]; x2 = groupind[x]; while(groupUpNode[x1] != -1){ res += x2 + 1; x = groupUpNode[x1]; x1 = group[x]; x2 = groupind[x]; } return res + x2; } int dist(int x, int y){ int x1; int y1; int x2; int y2; int res = 0; x1 = group[x]; x2 = groupind[x]; y1 = group[y]; y2 = groupind[y]; while(groupDepth[x1] > groupDepth[y1]){ res += x2 + 1; x = groupUpNode[x1]; x1 = group[x]; x2 = groupind[x]; } while(groupDepth[x1] < groupDepth[y1]){ res += y2 + 1; y = groupUpNode[y1]; y1 = group[y]; y2 = groupind[y]; } while(x1 != y1){ res += x2 + y2 + 2; x = groupUpNode[x1]; x1 = group[x]; x2 = groupind[x]; y = groupUpNode[y1]; y1 = group[y]; y2 = groupind[y]; } if(x2 <= y2){ return res + y2 - x2; } return res + x2 - y2; } int up(int x){ int x1 = group[x]; int x2 = groupind[x]; if(x2==0){ return groupUpNode[x1]; } return groupNode[x1][x2-1]; } int up(int x, int d){ int x1 = group[x]; int x2 = groupind[x]; while(d > x2){ if(groupUpNode[x1]==-1){ return -1; } d -= x2 + 1; x = groupUpNode[x1]; x1 = group[x]; x2 = groupind[x]; } return groupNode[x1][x2-d]; } } ; template struct HLD_fenwick{ HLD *hld; fenwick *fen; void init(HLD *hld__, void **mem = &wmem){ int i; int j; hld = hld__; walloc1d(&fen, hld->groupNum, mem); for(i=(0);i<(hld->groupNum);i++){ fen[i].walloc(hld->groupSize[i], mem); fen[i].init(hld->groupSize[i]); } } inline void add(int u, T val){ int ug; int ui; ug = hld->group[u]; ui = hld->groupind[u]; fen[ug].add(ui, val); } inline T get(int u, int v){ T res; int ug; int vg; int ui; int vi; ug = hld->group[u]; vg = hld->group[v]; res = 0; while(ug != vg){ if(hld->groupDepth[ug] < hld->groupDepth[vg]){ swap(u, v); swap(ug, vg); } res += fen[ug].get(hld->groupind[u]); u = hld->groupUpNode[ug]; ug = hld->group[u]; } ui = hld->groupind[u]; vi = hld->groupind[v]; res += fen[ug].range(min_L(ui, vi),max_L(ui, vi)); return res; } } ; int N; int A[100000]; int B[100000]; int C[100000]; int sz; int X[100000]; int dis[100000]; int pre[100000]; int val[100000]; int nx[100000]; int bf[100000]; int main(){ int KL2GvlyY; wmem = memarr; int i; int j; int k; int m; long long res; graph g; HLD hld; HLD_fenwick t; LHeap hp; rd(N); { int Lj4PdHRW; for(Lj4PdHRW=(0);Lj4PdHRW<(N-1);Lj4PdHRW++){ rd(A[Lj4PdHRW]); rd(B[Lj4PdHRW]); rd(C[Lj4PdHRW]); } } g.setEdge(N,N-1,A,B); hld.init(g); t.init(&hld); hp.walloc(N); g.getDist(0,dis); for(i=(0);i<(N-1);i++){ if(dis[A[i]] > dis[B[i]]){ swap(A[i], B[i]); } } for(i=(0);i<(N-1);i++){ t.add(B[i], C[i]); } g.preorder(val); for(i=(0);i<(N);i++){ pre[val[i]] = i; } int Q5VJL1cS = rd_int(); for(KL2GvlyY=(0);KL2GvlyY<(Q5VJL1cS);KL2GvlyY++){ int cTE1_r3A; rd(sz); { int e98WHCEY; for(e98WHCEY=(0);e98WHCEY<(sz);e98WHCEY++){ rd(X[e98WHCEY]); } } for(i=(0);i<(sz);i++){ val[i] = pre[X[i]]; } sortA_L(sz, val, X); hp.init(sz-1); for(i=(0);i<(sz-1);i++){ k = hld.lca(X[i],X[i+1]); hp.change(i, -dis[k]); } for(i=(0);i<(sz);i++){ bf[i] = i-1; } for(i=(0);i<(sz);i++){ nx[i] = i+1; } res = 0; for(cTE1_r3A=(0);cTE1_r3A<(sz-1);cTE1_r3A++){ i = hp.pop(); j = nx[i]; k = hld.lca(X[i], X[j]); res += t.get(X[i], k) - t.get(k,k); res += t.get(X[j], k) - t.get(k,k); X[j] = k; k = bf[j] = bf[i]; if(k >= 0){ nx[k] = j; } if(0 <= j && j < sz-1 && 0 <= nx[j] && nx[j] < sz){ m = hld.lca(X[j], X[nx[j]]); hp.change(j, -dis[m]); } if(0 <= k && k < sz-1 && 0 <= nx[k] && nx[k] < sz){ m = hld.lca(X[k], X[nx[k]]); hp.change(k, -dis[m]); } } wt_L(res); wt_L('\n'); } return 0; } // cLay varsion 20191006-1 // --- original code --- // int N, A[1d5], B[1d5], C[1d5]; // int sz, X[1d5]; // int dis[1d5], pre[1d5], val[1d5]; // // int nx[1d5], bf[1d5]; // // { // int i, j, k, m; // ll res; // graph g; // HLD hld; // HLD_fenwick t; // LHeap hp; // // rd(N,(A,B,C)(N-1)); // // g.setEdge(N,N-1,A,B); // hld.init(g); // t.init(&hld); // hp.walloc(N); // // g.getDist(0,dis); // rep(i,N-1) if(dis[A[i]] > dis[B[i]]) swap(A[i], B[i]); // rep(i,N-1) t.add(B[i], C[i]); // // g.preorder(val); // rep(i,N) pre[val[i]] = i; // // REP(rd_int()){ // rd(sz,X(sz)); // rep(i,sz) val[i] = pre[X[i]]; // sortA(sz, val, X); // hp.init(sz-1); // rep(i,sz-1){ // k = hld.lca(X[i],X[i+1]); // hp.change(i, -dis[k]); // } // rep(i,sz) bf[i] = i-1; // rep(i,sz) nx[i] = i+1; // res = 0; // rep(sz-1){ // i = hp.pop(); // j = nx[i]; // k = hld.lca(X[i], X[j]); // res += t.get(X[i], k) - t.get(k,k); // res += t.get(X[j], k) - t.get(k,k); // X[j] = k; // k = bf[j] = bf[i]; // if(k >= 0) nx[k] = j; // if(0 <= j < sz-1 && 0 <= nx[j] < sz){ // m = hld.lca(X[j], X[nx[j]]); // hp.change(j, -dis[m]); // } // if(0 <= k < sz-1 && 0 <= nx[k] < sz){ // m = hld.lca(X[k], X[nx[k]]); // hp.change(k, -dis[m]); // } // } // wt(res); // } // }