//by Tanmay Chaudhari #ifdef _MSC_VER #define _CRT_SECURE_NO_WARNINGS #endif //#pragma comment(linker, "/STACK:66777216") #include <bits/stdc++.h> using namespace std; #define si(a) scanf("%d",&a) #define sl(a) scanf("%lld",&a) #define pi(a) printf("%d\n",a) #define pl(a) printf("%lld\n",a) typedef long long ll; typedef vector<int> vi; typedef pair<int, int> ii; typedef vector<vi> vvi; typedef vector<ii> vii; #define SET(a,b) memset(a,b,sizeof(a)) #define forall(i,a,b) for(int i=a; i<b; i++) #define forrev(i,a,b) for(int i=a; i>=b; i--) #define forr(it,container) for(auto it=container.begin(); it!=container.end(); it++) #define w(t) int t;si(t);while(t--) #define TRACE #ifdef TRACE #define trace1(x) cerr << #x << ": " << x << endl; #define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl; #define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl; #define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl; #define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl; #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl; #else #define trace1(x) #define trace2(x, y) #define trace3(x, y, z) #define trace4(a, b, c, d) #define trace5(a, b, c, d, e) #define trace6(a, b, c, d, e, f) #endif set<pair<int, ll > > g[1 << 20]; int arr[1 << 20], k; int parent[1 << 20], tt; ll marked[1 << 20]; ll ans; bool vis[1 << 20]; pair<pair<ll, ll>, ll > pp[1 << 20]; /*int marked[1 << 20]; bool vis[1 << 20]; ll dfs(int v, int par, ll w) { vis[v] = 1; int n = g[v].size(); ll temp = 0; forall(i, 0, n) { int to = g[v][i].first; if (!vis[to]) temp += dfs(to, v, g[v][i].second); } temp += marked[v]; if (par != -1) ans += (k * 1LL - temp) * temp * w; return temp; } */ int sz, subsize_centroid[1 << 20]; int tin[1 << 20], tout[1 << 20], pv[1 << 20]; int timer, par[1 << 20][22]; vi tree[1 << 20]; ll dist[1 << 20]; void dfs(int v, ll _depth) { dist[v] = _depth; tin[v] = ++timer; par[v][0] = pv[v]; for (int i = 1; i <= 19; i++) par[v][i] = par[par[v][i - 1]][i - 1]; for (auto i = g[v].begin(); i != g[v].end(); i++) { int to = i->first; if (to == pv[v]) continue; pv[to] = v; dfs(to, _depth + i->second); } tout[v] = ++timer; } bool upper(int a, int b) { return (tin[a] <= tin[b] && tout[a] >= tout[b]); } int lca(int a, int b) { if (upper(a, b)) return a; if (upper(b, a)) return b; for (int i = 19; i >= 0; i--) if (!upper(par[a][i], b)) a = par[a][i]; return par[a][0]; } ll distance(int a, int b, int c) { return dist[a] + dist[b] - 2 * dist[c]; } void dfs1(int u, int par) { subsize_centroid[u] = 1; sz++; for (auto i = g[u].begin(); i != g[u].end(); i++) { int v = i->first; if (v != par) { dfs1(v, u); subsize_centroid[u] += subsize_centroid[v]; } } } int dfs2(int u, int par) { for (auto i = g[u].begin(); i != g[u].end(); i++) { int v = i->first; if (v != par && subsize_centroid[v] > sz / 2) return dfs2(v, u); } return u; } void decompose(int root, int p) { sz = 0; dfs1(root, root); int centroid = dfs2(root, root); //trace1(centroid); if (p == -1) p = centroid; parent[centroid] = p; for (auto i = g[centroid].begin(); i != g[centroid].end(); i++) { int v = i->first; ll sec = i->second; g[v].erase(make_pair(centroid, sec)); decompose(v, centroid); } g[centroid].clear(); } /*ll fff; ll extradfs(int child, int u, int par) { // trace2(child, par); if (pp[child].first.first<tt || pp[child].first.second == 0) return 0; ll temp=0; for (int i = 0; i < tree[child].size(); i++) { int to = tree[child][i]; if (to != par) { temp += extradfs(to, u, child); } } // trace2(temp, pp[child].first.second); if (temp < pp[child].first.second) fff += ((pp[child].first.second - temp)*distance(child, u, lca(child, u))); //trace1(fff); return pp[child].first.second; }*/ ll contri[1 << 20]; void build(int n) { for (int i = 0; i < n; i++) { if (i == parent[i]) continue; tree[i].push_back(parent[i]); tree[parent[i]].push_back(i); } } void func(int v) { int x = v; ll w = 0; int child = -1; ll childscnd = 0; ll childdist = 0; while (1) { // trace2(x, parent[x]); w = distance(x, v, lca(x,v)); if (pp[x].first.first < tt) { pp[x].first.first = tt; contri[x] = 0; if (child != -1) { contri[child] = w; //trace1(contri[child]); } pp[x].first.second = 1; pp[x].second = w; } else if (child == -1) { ans += pp[x].second - marked[v] * w + (pp[x].first.second - marked[v]) * w; childscnd = pp[x].second; pp[x].first.second += 1; pp[x].second += w; } else { //fff = 0; // trace1(child); //extradfs(child, x, x); // trace1(fff); //fff -= w; // trace1(fff); // trace5(pp[x].second, contri[child], pp[x].first.second, pp[child].first.second, w); ans += (pp[x].second - contri[child]) + (pp[x].first.second - pp[child].first.second + 1LL) * w; pp[x].first.second += 1; contri[child] += w; // trace1(contri[child]); childscnd = pp[x].second; pp[x].second += w; } // trace1(ans); childdist = distance(x, parent[x], lca(x, parent[x])); //trace2(childdist, lca(x, parent[x])); //trace3(pp[x].first.first, pp[x].first.second, pp[x].second); //w += childdist; if (x == parent[x]) break; child = x; x = parent[x]; } } int main() { //freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); int n, t; si(n); si(t); forall(i, 0, n - 1) { int a, b; ll c; si(a); si(b); sl(c); a--; b--; g[a].insert(make_pair(b, c)); g[b].insert(make_pair(a, c)); } dfs(0, 0); decompose(0, -1); // build(n); //forall(i, 0, n) // trace2(i, parent[i]); for (tt = 1; tt <= t; tt++) { ans = 0; si(k); forall(j, 0, k) { si(arr[j]); arr[j] -= 1; func(arr[j]); marked[arr[j]]++; } forall(j, 0, k) marked[arr[j]] = 0; pl(ans); } return 0; }