#pragma comment (linker, "/STACK:128000000") #include <iostream> #include <cstdio> #include <fstream> #include <functional> #include <set> #include <map> #include <vector> #include <queue> #include <stack> #include <cmath> #include <algorithm> #include <cstring> #include <bitset> #include <ctime> #include <sstream> #include <stack> #include <cassert> #include <list> #include <deque> using namespace std; #define mp make_pair #define pb push_back typedef __int128 li; typedef long long i64; typedef pair <int, int> pi; typedef vector <int> vi; typedef double ld; typedef vector<int> vi; typedef pair <int, int> pi; void solve(); //int timer = 0; #define FILENAME "" int main() { string s = FILENAME; #ifdef YA //assert(!s.empty()); freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); //cerr<<FILENAME<<endl; //assert (s != "change me please"); clock_t start = clock(); #else //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); //freopen(FILENAME ".in", "r", stdin); //freopen(FILENAME ".out", "w", stdout); cin.tie(0); #endif cout.sync_with_stdio(0); cout.precision(10); cout << fixed; int t = 1; //cin >> t; for (int i = 1; i <= t; ++i) { //++timer; //cout << "Case #" << i << ": "; solve(); } #ifdef YA cerr << "\n\n\n" << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n\n"; #endif return 0; } const int LOG = 17; int n, t; vector < vector < pair <int, int> > > g; vector <int> tin, tout, depth; vector <int> depth_v; vector <vector <int> > ancs; int TIMER = 0; void dfs(int v, int p = 0) { tin[v] = ++TIMER; ancs[v].resize(LOG); ancs[v][0] = p; for (int i = 1; i < ancs[v].size(); ++i) { ancs[v][i] = ancs[ancs[v][i - 1]][i - 1]; } for (auto edge : g[v]) { int to = edge.first; if (to == p) { continue; } depth[to] = depth[v] + edge.second; depth_v[to] = depth_v[v] + 1; dfs(to, v); } tout[v] = ++TIMER; } bool cmp_tin(int x, int y) { return tin[x] < tin[y]; } int go_up(int v, int d) { for (int i = 0; i < LOG; ++i) { if ((1 << i) & d) { v = ancs[v][i]; } } return v; } int get_lca(int x, int y) { if (depth_v[x] < depth_v[y]) { swap(x, y); } x = go_up(x, depth_v[x] - depth_v[y]); for (int i = LOG - 1; i >= 0; --i) { if (ancs[x][i] != ancs[y][i]) { x = ancs[x][i]; y = ancs[y][i]; } } return ancs[x][0]; } vector <int> sums; li ans = 0; int k; int build_g(int v, int par_edge, const vector <int>& all_v, int& shift) { int cursum = sums[v]; while (shift < all_v.size() && tout[all_v[shift]] < tout[v]) { int to = all_v[shift]; ++shift; cursum += build_g(to, depth[to] - depth[v], all_v, shift); } ans += (depth[v] - depth[all_v[0]]) * li(sums[v]) * li(k - 1); ans -= par_edge * li(cursum) * li(cursum - 1); return cursum; } void solve() { cin >> n >> t; g.resize(n); sums.resize(n); depth.resize(n); tin.resize(n); tout.resize(n); ancs.resize(n); depth_v.resize(n); for (int i = 0; i < n - 1; ++i) { int x, y, w; cin >> x >> y >> w; --x; --y; g[x].push_back(mp(y, w)); g[y].push_back(mp(x, w)); } dfs(0); for (int q = 0; q < t; ++q) { cin >> k; if (k == 0) { cout << 0 << "\n"; continue; } vector <int> verts(k); for (int i = 0; i < k; ++i) { cin >> verts[i]; --verts[i]; ++sums[verts[i]]; } sort(verts.begin(), verts.end(), cmp_tin); vector <int> all_verts = verts; for (int i = 1; i < verts.size(); ++i) { all_verts.push_back(get_lca(verts[i], verts[i - 1])); } sort(all_verts.begin(), all_verts.end(), cmp_tin); all_verts.erase(unique(all_verts.begin(), all_verts.end()), all_verts.end()); ans = 0; /*for (int v : verts) { ans += depth[v] * li(k - 1); }*/ int shift = 1; build_g(all_verts[0], 0, all_verts, shift); cout << (long long) ans << "\n"; for (int v : verts) { --sums[v]; } } }