#include <iostream> #include <algorithm> #include <memory.h> #include <cstring> #include <sstream> #include <cstdlib> #include <complex> #include <string> #include <bitset> #include <vector> #include <cstdio> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define ll long long const int N = 100005; // long long ANS[N]; // int dsu[N], ancestor[N]; // bool u[N]; vector < pair < int, int > > g[N]; // vector<pair<int, pair<int, long long>>> q[N]; int dp[N]; // namespace Fdg { // inline int dsu_get (int v) { // return v == dsu[v] ? v : dsu[v] = dsu_get (dsu[v]); // } // inline void dsu_unite (int a, int b, int new_ancestor) { // a = dsu_get (a), b = dsu_get (b); // if (rand() & 1) swap (a, b); // dsu[a] = b, ancestor[b] = new_ancestor; // } // inline void dfs (int v) { // dsu[v] = v, ancestor[v] = v; // u[v] = true; // for (size_t i=0; i<g[v].size(); ++i) // if (!u[g[v][i].first]) { // dfs (g[v][i].first); // dsu_unite (v, g[v][i].first, v); // } // for (size_t i=0; i<q[v].size(); ++i) // if (u[q[v][i].first]) { // // printf ("%d %d -> %d\n", v+1, q[v][i].first+1, // // ancestor[ dsu_get(q[v][i].first) ]+1); // ANS[q[v][i].second.first] -= 2LL * q[v][i].second.second * dp[ancestor[dsu_get(q[v][i].first)]]; // } // } // } int start = 0; vector<int> perm; // int dist[N]; int pr[18][N]; int timer; int pe[N], f[N], par[N], parc[N]; int arr[10 * N]; const int SMALL = 100; pair < int, int > cnt[N]; int tin[N], tout[N]; int n, m; inline bool pred(int a, int b) { return tin[a] <= tin[b] && tout[b] <= tout[a]; } inline int lca(int a, int b) { if (pred(a, b)) return a; if (pred(b, a)) return b; int i = 10; for (int i = 10; i >= 0; --i) while (!pred(pr[i][a], b)) a = pr[i][a]; return pr[0][a]; } inline void dfs(int x, int p) { tin[x] = ++timer; par[x] = p; // cout << x << " " << par[x] << endl; pr[0][x] = (p == -1) ? start : p; for (int i = 1; i <= 16; ++i) pr[i][x] = pr[i - 1][pr[i - 1][x]]; for (auto &e : g[x]) { if (e.first == p) continue; dp[e.first] = dp[x] + e.second; parc[e.first] = e.second; dfs(e.first, x); } tout[x] = ++timer; } inline int D(int a, int b) { int l = lca(a, b); // cout << a << " " << b << " " << l << endl; return dp[a] + dp[b] - 2 * dp[l]; } int need[N]; int TMP = 1; ll res = 0; inline void run(int x, int p) { pe[x] = f[x]; if (need[x] != TMP) return; for (auto &e : g[x]) { if (e.first == p) continue; run(e.first, x); if (pe[e.first] && pe[e.first] != m) { res += 1LL * pe[e.first] * (m - pe[e.first]) * e.second; pe[x] += pe[e.first]; } if (pe[x] == m) return; } } int what[10 * N]; // map<int, long long> mem; pair<int, int> all[N]; inline void solve(int index) { ++TMP; scanf("%d", &m); long long h = 0; for (int i = 0; i < m; ++i) { int a; scanf("%d", &a); a--; a = perm[a]; arr[a]++; what[i] = a; } // sort(arr, arr + m); // int sz = 0; // for (int i = 0; i < m;) { // int j = i; // while (j < m && arr[i] == arr[j]) j++; // cnt[sz++] = make_pair(arr[i], j - i); // i = j; // } int sz = 0; for (int i = 0; i < m; ++i) { int x = what[i]; if (arr[x]) { cnt[sz++] = {x, arr[x]}; arr[x] = 0; // h = (1LL * h * 1000013 + x + 11) % 1000000007; // h = (1LL * h * 1000013 + arr[x] + 11) % 1000000007; } } // if (mem.count(h)) { // printf("%lld\n", mem[h]); // return; // } if (sz <= 100) { ll ans = 0; for (int i = 0; i < sz; ++i) { for (int j = i + 1; j < sz; ++j) { int d = D(cnt[i].first, cnt[j].first); ans += 1LL * d * cnt[i].second * cnt[j].second; // if (pred(cnt[i].first, cnt[j].first)) // ANS[index] -= 2LL * dp[cnt[i].first] * cnt[i].second * cnt[j].second; // else if (pred(cnt[j].first, cnt[i].first)) // ANS[index] -= 2LL * dp[cnt[j].first] * cnt[i].second * cnt[j].second; // else { // q[cnt[i].first].push_back({cnt[j].first, {index, 1LL * cnt[i].second * cnt[j].second}}); // q[cnt[j].first].push_back({cnt[i].first, {index, 1LL * cnt[i].second * cnt[j].second}}); // } } } printf("%lld\n", ans); } else { res = 0; int SIZE = 0; for (int i = 0; i < sz; ++i) { f[cnt[i].first] += cnt[i].second; int cur = cnt[i].first; while (cur != -1 && need[cur] != TMP) { need[cur] = TMP; all[SIZE++] = {-dp[cur], cur}; cur = par[cur]; } } sort(all, all + SIZE); for (int i = 0; i < SIZE; ++i) { if (par[all[i].second] != -1) { res += 1LL * f[all[i].second] * (m - f[all[i].second]) * parc[all[i].second]; f[par[all[i].second]] += f[all[i].second]; } } // run(start, -1); // mem[h] = res; printf("%lld\n", res); // ANS[index] = res; for (int i = 0; i < SIZE; ++i) f[all[i].second] = 0; } } int main() { //freopen("input.txt", "r", stdin); int t; scanf("%d%d", &n, &t); srand(time(NULL)); for (int i = 0; i < n; ++i) perm.push_back(i); random_shuffle(perm.begin(), perm.end()); // random_shuffle(perm.begin(), perm.end()); // random_shuffle(perm.begin(), perm.end()); // random_shuffle(perm.begin(), perm.end()); // random_shuffle(perm.begin(), perm.end()); for (int i = 0; i < n - 1; ++i) { int x, y, c; scanf("%d%d%d", &x, &y, &c); x--; y--; x = perm[x]; y = perm[y]; g[x].emplace_back(make_pair(y, c)); g[y].emplace_back(make_pair(x, c)); } // memset(par, -1, sizeof(par)); // start = (rand() * RAND_MAX + rand()) % n; dfs(start, -1); for (int i = 0; i < t; ++i) { solve(i); } // Fdg::dfs(0); // for (int i = 0; i < t; ++i) { // printf("%lld\n", ANS[i]); // } return 0; }