/* ----------------------------------------------------------------------------- Author : --------------------------------------------------------- UTKAR$H $AXENA --------------------------------------------------------- IIT INDORE --------------------------------------------------------- ----------------------------------------------------------------------------- */ #include<bits/stdc++.h> #include<iostream> using namespace std; #define fre freopen("0.in","r",stdin),freopen("0.out","w",stdout) #define abs(x) ((x)>0?(x):-(x)) #define MOD 1000000007 #define lld unsigned long long int #define pp pop_back() #define ps(x) push_back(x) #define mpa make_pair #define pii pair<int,int> #define fi first #define se second #define print(x) printf("%d\n",x) #define scanll(x) scanf("%lld",&x) #define printll(x) printf("%lld\n",x) #define boost ios_base::sync_with_stdio(0) vector<int> G[100000+5]; vector<int> W[100000+5]; int path[100000+5]; int parentCentroid[100000+5]; lld contribution[100000+5]; vector<int>graphCentroid[100000+5]; int dead[100000+5],child[100000+5]; #define getcx getchar_unlocked inline void scan( int &n ) { n=0; int ch=getcx();int sign=1; while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();} while( ch >= '0' && ch <= '9' ) n = (n<<3)+(n<<1) + ch-'0', ch=getcx(); n=n*sign; } int sizeOfSubtree(int v,int parent){ if(dead[v]) return 0; int temp = 1; for(int i=0;i<G[v].size();++i){ int u = G[v][i]; if(u!=parent){ temp += sizeOfSubtree(u,v); } } return (child[v] = temp); } int findCentroid(int v,int parent,int sizeOfComponent){ if(dead[v]) return 0; int largestChild = sizeOfComponent - child[v] ; for(int i=0;i<G[v].size();++i){ int u = G[v][i]; if(parent==u or dead[u]) continue; largestChild = max(largestChild,child[u]); int temp = findCentroid(u,v,sizeOfComponent); if(temp>0) return temp; } if(largestChild <= sizeOfComponent/2){ return v; } else{ return 0; } } void buildCentroidTree(int v,int parentInCentroidTree){ int currentCentroid = findCentroid(v,0,sizeOfSubtree(v,0)); parentCentroid[currentCentroid] = parentInCentroidTree; graphCentroid[parentInCentroidTree].push_back(currentCentroid); dead[currentCentroid] = 1; for(int i=0;i<G[currentCentroid].size();++i){ int u = G[currentCentroid][i]; if(dead[u]) continue; buildCentroidTree(u,currentCentroid); } } /* LCA lcaDPART */ int parentLCA[100000+5],lcaDP[100000+5][18],levelLCA[100000+5]; void dfsLCA(int v,int lev,int dist) { levelLCA[v]=lev; path[v] = dist; for(int i=0; i<G[v].size(); ++i) { int u=G[v][i]; if(parentLCA[v]==u)continue; parentLCA[u]=v; dfsLCA(u,lev+1,dist+W[v][i]); } } void createLCA(int n) { int i, j; dfsLCA(1,0,0); for (i = 1; i<=n; i++) for (j = 0; (1<<j) <=n; j++) lcaDP[i][j] = -1; for (i=1; i<=n; i++) lcaDP[i][0] = parentLCA[i]; for (j = 1; (1<<j) <=n; j++) for (i = 1; i <=n; i++) if (lcaDP[i][j - 1] != -1) lcaDP[i][j] = lcaDP[lcaDP[i][j - 1]][j - 1]; } int lca(int p, int q) { int tmp, log, i; if (levelLCA[p] < levelLCA[q]) tmp = p, p = q, q = tmp; for (log = 1; 1 << log <= levelLCA[p]; log++); log--; for (i = log; i >= 0; i--) if ( levelLCA[p] - (1<<i) >= levelLCA[q] ) p = lcaDP[p][i]; if (p == q) return p; for (i = log; i >= 0; i--) if (lcaDP[p][i] != -1 && lcaDP[p][i] != lcaDP[q][i]) p = lcaDP[p][i], q = lcaDP[q][i]; return parentLCA[p]; } int distanceTree(int p,int q) { if(p==0 or q==0) return 0; return path[p] + path[q] - 2*path[lca(p,q)]; } /* LCA FINISHES */ int mem_distance[100000+5][25]; lld sum[100000+5]; int freq[100000+5]; lld query(int v){ lld ans = sum[v]; int par, p = v; int co=0; while(p!=0){ par = parentCentroid[p]; ans += (sum[par]-contribution[p])+(lld)mem_distance[v][co+1]*(freq[par]-freq[p]); co++; p = parentCentroid[p]; } return ans; } void update(int v,int x){ int p = v; int child = 0; lld temp; int co=0; while(p!=0){ freq[p] += x; temp=(lld)mem_distance[v][co]*x; co++; sum[p] += temp; contribution[child] += temp; child=p; p = parentCentroid[p]; } } void cool(int v){ int p = v; while(p!=0 and freq[p]>0){ freq[p]=0; sum[p] =0; contribution[p]=0; p = parentCentroid[p]; } } int temp[1000000+5]; int occ[100000+5]; int main() { //fre; int N,M,a,b,c,option,x; cin>>N>>M; for(int i=1;i<N;++i){ scan(a); scan(b); scan(c); G[a].push_back(b); G[b].push_back(a); W[a].push_back(c); W[b].push_back(c); } buildCentroidTree(1,0); createLCA(N); for(int i=1;i<=N;++i) { int p=i; int co=0; while(p!=0){ mem_distance[i][co] = distanceTree(p,i); p = parentCentroid[p]; ++co; } } int T; lld ans = 0; while(M--){ scan(T); ans = 0; for(int i=1;i<=T;++i){ scan(temp[i]); occ[temp[i]]++; } for(int i=1;i<=T;++i){ if(occ[temp[i]]!=0){ ans += query(temp[i])*occ[temp[i]]; update(temp[i],occ[temp[i]]); occ[temp[i]]=0; } } printll(ans); for(int i=1;i<=T;++i){ cool(temp[i]); } } }