#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <cstdio> #include <cstdlib> #include <stack> #include <cstring> #include <iomanip> #include <cctype> #include <map> #include <cassert> using namespace std; const int N = 100005; int p[100005][41]; // p[i][j] stores i's 2ˆj th parent vector<vector<pair<int,long long> > > Tree; int level[N]; long long dist[N]; int n; int startTime[N]; int finishTime[N]; int ti = 0; #define x first #define y second //helper dfs to fill out immaediate parent and level of vertices void dfs(int u,int pa,int cl) { p[u][0] = pa; level[u] = cl; ti++; startTime[u] = ti; if(pa == 0) dist[u] = 0; for(int i = 0;i < Tree[u].size();i++) { if(Tree[u][i].first != pa) { dist[Tree[u][i].first] = dist[u] + Tree[u][i].second; dfs(Tree[u][i].first,u,cl + 1); } } ti++; finishTime[u] = ti; } //helper dfs called and array p filled void preprocess() { dfs(1,0,1); for(int i = 0;i <= n;i++) { for(int j = 1;j <= 40;j++) p[i][j] = 0; } for(int j = 1;j <= 40;j++) { for(int i = 1;i <= n;i++) { p[i][j] = p[p[i][j - 1]][j - 1]; } } } //Calculates lowest common ancestor of u and v int lca(int u,int v) { if(level[u] < level[v]) swap(u,v); // Have u at a lower level int log = 0; while( (1<<log) < (level[u] - level[v]) ) log++; for(int i = log;i >= 0;i--) { if(level[u] - (1<<i) >= level[v] ) u = p[u][i]; //bringing u to v's level } if(u == v) return u; log = 0; //finding lca while((1<<log) <= level[u] ) log++; for(int i = log;i >= 0;i--) { if(p[u][i] != 0 && p[u][i] != p[v][i]) { u = p[u][i]; v = p[v][i]; } } return p[u][0]; } struct info { int vertex; long long numOfVert; long long sumOfVert; bool operator<(const info& i) const { return startTime[vertex] < startTime[i.vertex]; } }; long long ans = 0; int s[1000005]; info combine(info a,info b) { info l; l.vertex = lca(a.vertex,b.vertex); l.numOfVert = a.numOfVert + b.numOfVert; l.sumOfVert = a.sumOfVert + b.sumOfVert + a.numOfVert * (dist[a.vertex] - dist[l.vertex]) + b.numOfVert * (dist[b.vertex] - dist[l.vertex]); long long commonPath = dist[a.vertex] + dist[b.vertex] - 2LL * dist[l.vertex]; ans+=a.numOfVert * b.numOfVert * commonPath; ans+=a.numOfVert * b.sumOfVert + b.numOfVert * a.sumOfVert; return l; } typedef multiset<info>::iterator msi; void solve() { int k; scanf("%d",&k); map<int,int> mp; for(int i = 0;i < k;i++) { scanf("%d",&s[i]); mp[s[i]]++; } ans = 0; multiset<info> ms; k = (int)mp.size(); for(map<int,int>::iterator it = mp.begin();it != mp.end();it++) { info tmp; tmp.vertex = it->first; tmp.sumOfVert = 0; tmp.numOfVert = it->second; ms.insert(tmp); } msi it = ms.begin(); while(ms.size() > 1) { if(it == ms.begin()) { it++; continue; } msi prev = it; prev--; msi nxt = it; nxt++; if(nxt == ms.end()) { msi prev = it; prev--; info tmp = combine(*prev,*it); ms.erase(prev); ms.erase(it); ms.insert(tmp); it = ms.find(tmp); continue; } if(finishTime[lca(prev->vertex,it->vertex)] <= startTime[nxt->vertex]) { info tmp = combine(*prev,*it); ms.erase(prev); ms.erase(it); ms.insert(tmp); it = ms.find(tmp); } else { it++; } } assert(ans >= 0); cout<<ans<<endl; } int main() { cin>>n; int t; cin>>t; Tree.resize(n + 1); for(int i = 1;i < n;i++) { int x,y; long long w; scanf("%d %d",&x,&y); scanf("%lld",&w); Tree[x].push_back({y,w}); Tree[y].push_back({x,w}); } preprocess(); while(t--) { solve(); } }