#include <iostream> #include <cmath> #include <string> #include <algorithm> #include <cstring> #include <cstdio> #include <fstream> #include <cassert> #include <map> #include <set> #include <vector> #include <queue> #include <stack> #include <functional> #include <numeric> #include <ctime> #include <cstdlib> #include <sstream> using namespace std; #define f first #define s second #define mp make_pair #define pb push_back #define pii pair<int, int> #define pll pair<long long, long long> #define y1 stupid_y1 #define ll long long #define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++) #define all(a) a.begin(), a.end() #define sqr(x) ((x)*(x)) #define sz(a) (int)a.size() #define file "a" const int inf = (int)1e9; const double eps = 1e-9; const double pi = acos(-1.0); int n, m; vector < pii > g[100100]; ll dist[100100]; int P[20][100100]; int parent[100100]; int S[1001000]; vector < int > ver; vector < pii > G[100100]; int timer; int tin[100100], tout[100100]; int position; int otec[100100]; int special[100100]; int level[100100]; int d1[100100], d2[100100]; int N; void precalc_lca(){ memset(P, -1, sizeof(P)); for (int i=1;i<=n;i++) P[0][i] = parent[i]; for (int j=1;j<20;j++){ for (int i=1;i<=n;i++){ if ( P[j-1][i] != -1 ) P[j][i] = P[j-1][P[j-1][i]]; } } } int getlca(int x, int y){ for (int i=19;i>=0;i--){ if ( level[x] - (1<<i) >= level[y]) x = P[i][x]; if ( level[y] - (1<<i) >= level[x]) y = P[i][y]; } if ( x == y ) return x; for (int j=19;j>=0;j--){ if ( P[j][x] != P[j][y] && P[j][x] != -1 && P[j][y] != -1){ x = P[j][x]; y = P[j][y]; } } return parent[x]; } void dfs(int v, int p, int depth, ll total){ tin[v] = timer++; level[v] = depth; dist[v] = total; parent[v] = p; forit(it, g[v]){ int to = (*it).f; int cost = (*it).s; if ( to == p ) continue; dfs(to, v, depth+1, total + cost); } tout[v] = timer++; } bool ischild(int i, int j){ return tin[i] < tin[j] && tout[j] < tout[i]; } bool cmp(int i, int j){ return tin[i] < tin[j]; } void make_graph(int v){ if ( position == sz(ver) ) return; if ( ischild(v, ver[position])){ int to = ver[position++]; otec[to] = v; ll cost = dist[to] - dist[v]; G[v].pb(mp(to, cost)); G[to].pb(mp(v, cost)); make_graph(to); } else { make_graph(otec[v]); } } void dfs1(int v, int p){ d1[v] = special[v]; forit(it, G[v]){ int to = (*it).f; ll cost = (*it).s; if ( to == p ) continue; dfs1(to, v); d1[v] += d1[to]; } } void dfs2(int v, int p, ll &ans){ forit(it, G[v]){ int to = (*it).f; ll cost = (*it).s; if ( to == p ) continue; d2[to] = d2[v] + d1[v] - d1[to]; //cout <<v<<" "<<to<<" "<<cost<<" "<<d1[to]<<" "<<d2[to]<<endl; ans += cost*d2[to]*d1[to]; dfs2(to, v, ans); } } void process(){ scanf("%d", &N); ver.clear(); for (int i=0;i<N;i++){ scanf("%d", &S[i]); special[S[i]]++; ver.pb(S[i]); } sort(S, S + N, cmp); for (int i=1;i<N;i++){ ver.pb(getlca(S[i-1], S[i])); } sort(all(ver)); ver.resize(unique(all(ver)) - ver.begin()); sort(all(ver), cmp); position = 1; make_graph(ver[0]); int root = ver[0]; dfs1(root, -1); ll ans = 0; dfs2(root, -1, ans); printf("%lld\n", ans); // clearing // d1 d2 otec G forit(it, ver){ d1[*it] = 0; d2[*it] = 0; G[*it].clear(); otec[*it] = 0; special[*it] = false; } } int main () { #ifdef LOCAL freopen(file".in", "r", stdin); freopen(file".out", "w", stdout); #endif scanf("%d%d", &n, &m); int a, b, c; for (int i=0;i<n-1;i++){ scanf("%d%d%d", &a, &b, &c); g[a].pb(mp(b, c)); g[b].pb(mp(a, c)); } dfs(1, -1, 0, 0); precalc_lca(); for (int ii=0;ii<m;ii++){ process(); } #ifdef LOCAL cerr << (double)clock() * 1.0 / CLOCKS_PER_SEC << endl; #endif return 0; }