#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 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[3]; int dis[100001]; int pre[100000]; int val[100000]; int main(){ int KL2GvlyY; wmem = memarr; int i; int j; int k; long long res; graph g; HLD hld; HLD_fenwick t; 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); g.getDist(0,dis); dis[N] = -1073709056; 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++){ sz = 3; { 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); res = 0; while(sz > 1){ if(sz==2){ i =N; } else{ i =hld.lca(X[sz-3], X[sz-2]); } j = hld.lca(X[sz-2], X[sz-1]); if(dis[i] < dis[j]){ if(j != X[sz-2]){ res += t.get(j, X[sz-2]) - t.get(j,j); } if(j != X[sz-1]){ res += t.get(j, X[sz-1]) - t.get(j,j); } X[sz-2] = j; } else{ if(i != X[sz-3]){ res += t.get(i, X[sz-3]) - t.get(i,i); } if(i != X[sz-2]){ res += t.get(i, X[sz-2]) - t.get(i,i); } if(sz != 2){ X[sz-3] = X[sz-1]; } X[sz-2] = i; } sz--; } wt_L(res); wt_L('\n'); } return 0; } // cLay varsion 20190929-1 // --- original code --- // int N, A[1d5], B[1d5], C[1d5]; // int sz, X[3]; // int dis[100001], pre[1d5], val[1d5]; // { // int i, j, k; // ll res; // graph g; // HLD hld; // HLD_fenwick t; // rd(N,(A,B,C)(N-1)); // // g.setEdge(N,N-1,A,B); // hld.init(g); // t.init(&hld); // // g.getDist(0,dis); // dis[N] = -int_inf; // 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()){ // sz = 3; // rd(X(sz)); // rep(i,sz) val[i] = pre[X[i]]; // sortA(sz, val, X); // res = 0; // while(sz > 1){ // i = if[sz==2, N, hld.lca(X[sz-3], X[sz-2])]; // j = hld.lca(X[sz-2], X[sz-1]); // if(dis[i] < dis[j]){ // if(j != X[sz-2]) res += t.get(j, X[sz-2]) - t.get(j,j); // if(j != X[sz-1]) res += t.get(j, X[sz-1]) - t.get(j,j); // X[sz-2] = j; // } else { // if(i != X[sz-3]) res += t.get(i, X[sz-3]) - t.get(i,i); // if(i != X[sz-2]) res += t.get(i, X[sz-2]) - t.get(i,i); // if(sz != 2) X[sz-3] = X[sz-1]; // X[sz-2] = i; // } // sz--; // } // wt(res); // } // }