#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <vector> using namespace std; #define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++) #define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--) #define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--) #define DRI(a) int a; scanf("%d ", &a); #define DRII(a, b) int a, b; scanf("%d %d ", &a, &b); #define DRIII(a, b, c) int a, b, c; scanf("%d %d %d ", &a, &b, &c); #define DRIIII(a, b, c, d) int a, b, c, d; scanf("%d %d %d %d ", &a, &b, &c, &d); #define RI(a) scanf("%d ", &a); #define RII(a, b) scanf("%d %d ", &a, &b); #define RIII(a, b, c) scanf("%d %d %d ", &a, &b, &c); #define RIIII(a, b, c, d) scanf("%d %d %d %d ", &a, &b, &c, &d); #define PB push_back #define MP make_pair #define ff first #define ss second #define vi vector<int> #define vll vector<ll> #define pii pair<int,int> #define ll long long #define ull unsigned long long #define MM(co, cim) memset((co), (cim), sizeof((co))) #define DEB(x) cerr << ">>> " << #x << " : " << x << endl; #define MAX 100007 int preOrder[100007]; vi g[100007]; vll gc[100007]; #define MAX 100007 #define MAXLOG 20 int depth[MAX]; ll dist[MAX]; int par[MAX][MAXLOG]; void lcaDFS(int v, int p, int de, ll di) { par[v][0] = p; depth[v] = de++; dist[v] = di; FOR(i,0,g[v].size()) { int u = g[v][i]; if(u == p) continue; lcaDFS(u,v,de,di+gc[v][i]); } } int parent(int a, int b) { if(depth[a] > depth[b]) swap(a,b); int diff = depth[b] - depth[a]; int sh = 0; while(diff) { if(diff & 1) b = par[b][sh]; diff >>= 1; sh++; } FORDE(i,19,0) { if(par[a][i] != par[b][i]) { a = par[a][i]; b = par[b][i]; } } if(a == b) return a; return par[a][0]; } int preOrderCnt; void DFSpo(int v, int p) { preOrder[v] = preOrderCnt++; FOR(i,0,g[v].size()) { int u = g[v][i]; if(p == u) continue; DFSpo(u,v); } } vi interUnique; // ok vi interAll; // ok bool cmpPE(const int& a, const int& b) { return preOrder[a] < preOrder[b]; } int LE[MAX], RI[MAX]; // ok class cmppq { public: bool operator() (const int& a, const int& b) const { return depth[interUnique[a]] < depth[interUnique[b]]; } }; vi gg[100007]; // ok int ggpar[100007]; // ok void makeGG(int v, int p) { if(v == p) return; if(ggpar[v] == -1) { ggpar[v] = p; } else if(depth[p] > depth[ggpar[v]]) { ggpar[v] = p; } } ll res; // ok ll countx[MAX]; // ok bool vis[MAX]; ll totalCount; // ok ll DFS(int v) { //DEB(v); ll retCnt = 0; FOR(i,0,gg[v].size()) { int u = gg[v][i]; ll cnt = DFS(u); res += cnt * (totalCount-cnt) * (dist[u] - dist[v]); //DEB(res); retCnt += cnt; } //DEB(countx[v]); retCnt += countx[v]; //DEB(retCnt); return retCnt; } void DFSclear(int v) { FOR(i,0,gg[v].size()) { int u = gg[v][i]; DFSclear(u); } countx[v] = 0; ggpar[v] = -1; gg[v].clear(); vis[v] = false; } int main () { MM(vis,false); MM(ggpar,-1); DRII(N,T); FOR(i,1,N) { DRII(A,B); ll C; cin >> C; g[A].PB(B); gc[A].PB(C); g[B].PB(A); gc[B].PB(C); } lcaDFS(1,0,0,0); FOR(i,1,MAXLOG) FOR(j,1,N+1) par[j][i] = par[par[j][i-1]][i-1]; preOrderCnt = 0; DFSpo(1,0); while(T--) { interUnique.clear(); interAll.clear(); DRI(K); FOR(i,0,K) { DRI(a); interUnique.PB(a); interAll.PB(a); } sort(interUnique.begin(), interUnique.end()); vi::iterator it = unique(interUnique.begin(), interUnique.end()); interUnique.resize(distance(interUnique.begin(),it)); sort(interUnique.begin(), interUnique.end(), cmpPE); FOR(i,1,interUnique.size()-1) { LE[i] = i-1; RI[i] = i+1; } int sz = interUnique.size(); if(sz == 1) { LE[0] = -1; RI[0] = -1; } else { LE[0] = -1; RI[0] = 1; LE[sz-1] = sz-2; RI[sz-1] = -1; } priority_queue<int, vector<int>, cmppq> pq; FOR(i,0,sz) { pq.push(i); } int root; while(!pq.empty()) { int pos = pq.top(); pq.pop(); int lepos = LE[pos]; int ripos = RI[pos]; int me = interUnique[pos]; //DEB(me); //DEB(lepos); //DEB(ripos); if(lepos == -1 && ripos == -1) { // Im root //cout << "root: " << me << endl; root = me; } else if(lepos == -1) { int ri = interUnique[ripos]; int rpar = parent(me,ri); if(rpar == ri) { LE[ripos] = -1; } else { interUnique[pos] = rpar; pq.push(pos); } makeGG(me,rpar); } else if(ripos == -1) { int le = interUnique[lepos]; int lpar = parent(me,le); if(lpar == le) { RI[lepos] = -1; } else { interUnique[pos] = lpar; pq.push(pos); } makeGG(me,lpar); } else { int le = interUnique[lepos]; int ri = interUnique[ripos]; int lpar = parent(me,le); int rpar = parent(me,ri); //DEB(lpar); //DEB(rpar); int par = lpar; if(depth[rpar] > depth[lpar]) par = rpar; if(par == le) { RI[lepos] = ripos; LE[ripos] = lepos; } else if(par == ri) { RI[lepos] = ripos; LE[ripos] = lepos; } else { interUnique[pos] = par; pq.push(pos); } makeGG(me,par); } } /* FOR(i,0,MAX) { if(ggpar[i] != -1) cout << i << ": " << ggpar[i] << endl; } */ queue<int> q; FOR(i,0,interAll.size()) { q.push(interAll[i]); countx[interAll[i]]++; } while(!q.empty()) { int v = q.front(); q.pop(); if(vis[v]) continue; vis[v] = true; int p = ggpar[v]; gg[p].PB(v); q.push(p); } totalCount = interAll.size(); res = 0; DFS(root); cout << res << endl; DFSclear(root); } return 0; }