/* * * File: stuff.cpp * Author: Andy Y.F. Huang (azneye) * Created on Aug 23, 2014, 11:50:25 PM */ #include <bits/stdc++.h> using namespace std; namespace stuff { typedef long long ll; static const int MAX = 100111; static const int LIM = 800; int head[MAX], to[2 * MAX], pred[2 * MAX], len[2 * MAX]; int dist[MAX], par[MAX]; int euler[2 * MAX], level[2 * MAX], pos[2 * MAX]; int rmq[18][2 * MAX], high_bit[2 * MAX]; int post[MAX], cnt[MAX], par_len[MAX]; int get_lca(int a, int b) { if (pos[a] > pos[b]) { swap(a, b); } const int bit = high_bit[pos[b] - pos[a] + 1]; const int x = rmq[bit][pos[a]]; const int y = rmq[bit][pos[b] - (1 << bit) + 1]; if (level[x] < level[y]) { return euler[x]; } else { return euler[y]; } } void dfs(int at) { static int cur_time = 0, post_len = 0; euler[cur_time] = at; level[cur_time] = dist[at]; pos[at] = cur_time++; for (int e = head[at]; ~e; e = pred[e]) { if (to[e] != par[at]) { par[to[e]] = at; dist[to[e]] = dist[at] + len[e]; par_len[to[e]] = len[e]; dfs(to[e]); euler[cur_time] = at; level[cur_time++] = dist[at]; } } post[post_len++] = at; } void solve(int test_num) { int N, Q; scanf("%d %d", &N, &Q); memset(head, -1, sizeof(head)); for (int e = 0, a, b; e < N - 1; ++e) { scanf("%d %d %d", &a, &b, len + e + e); len[e + e + 1] = len[e + e]; to[e + e] = b; pred[e + e] = head[a]; head[a] = e + e; to[e + e + 1] = a; pred[e + e + 1] = head[b]; head[b] = e + e + 1; } dist[1] = 0; dfs(1); const int L = 2 * N - 1; for (int bit = 0; (1 << bit) <= L; ++bit) { for (int i = (1 << bit); i < 2 * (1 << bit) && i <= L; ++i) { high_bit[i] = bit; } } for (int i = 0; i < L; ++i) { rmq[0][i] = i; } for (int j = 0; j < 17; ++j) { for (int i = 0; i < L; ++i) { const int a = rmq[j][i]; const int b = rmq[j][min(L - 1, i + (1 << j))]; if (level[a] < level[b]) { rmq[j + 1][i] = a; } else { rmq[j + 1][i] = b; } } } for (int qq = 0, K; qq < Q; ++qq) { scanf("%d", &K); static int ver[10 * MAX]; for (int i = 0; i < K; ++i) { scanf("%d", ver + i); } ll res = 0; if (K <= LIM) { sort(ver, ver + K); for (int i = 0; i < K; ++i) { res += (K - 1LL) * dist[ver[i]]; for (int j = i + 1; j < K; ++j) { const int lca = get_lca(ver[i], ver[j]); //pln(ver[i], ver[j], lca); res -= 2 * dist[lca]; } } } else { memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < K; ++i) { cnt[ver[i]]++; } for (int i = 0; i < N - 1; ++i) { const int v = post[i]; cnt[par[v]] += cnt[v]; res += ll(cnt[v]) * (K - cnt[v]) * par_len[v]; } } printf("%lld\n", res); } } void solve() { #ifdef AZN //make_case(); double start_t = clock(); freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); //freopen("azn.txt", "w", stderr); #endif ios::sync_with_stdio(false); cin.tie(NULL); int T = 1; //scanf("%d", &T); //cin >> T; for (int t = 1; t <= T; t++) solve(t); #ifdef AZN cerr << fixed << setprecision(3) << "Took: " << ((clock() - start_t) / CLOCKS_PER_SEC); #endif } } int main() { stuff::solve(); return 0; }