#include<bits/stdc++.h> using namespace std; #define in(a,x,y) (x <= a && a <= y) #define sz(a) (int)a.size() #define rep(i,a,b) for(int i = a; i <= b; i++) #define rev(i,a,b) for(int i = a; i >= b; i--) #define repv(i,a) for(int i = 0; i < sz(a); i++) #define max(a,b) (a > b ? a : b) #define all(a) a.begin(), a.end() #define mp make_pair #define pb push_back #define xx first #define yy second #define inf 2e9 #define MX 100100 #define LB(a, x) lower_bound(all(a), x) - a.begin() #define UB(a, x) upper_bound(all(a), x) - a.begin() typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vll; template <class X, class Y> bool getbit(X b, Y i) {return (b & (1ll << i)) > 0;} template <class X, class Y> X setbit(X b, Y i) {return (b | (1ll << i));} template <class X> void unify(X &a) {sort(all(a)); a.erase(unique(all(a)), a.end());} template< class T,class X, class Y > inline T bigmod(T n,X m,Y mod){ull ret=1, a = n%mod ; while(m){ if(m&1)ret=(ret*a)%mod; m>>=1; a=(a*a)%mod; }ret%=mod;return (T)ret;} template< class T, class Y > inline T modinv(T n,Y mod) {return bigmod(n,mod-2,mod);} #define mid ((st + ed) >> 1) #define lft (idx << 1) #define rgt (lft | 1) struct data { ll s, n, r, l; data() {s = n = r = l = 0;} data(ll ss, ll nn, ll rr, ll _l) {s = ss, n = nn, r = rr, l = _l;} }; int n, dep[MX], par[MX], weight[MX], sz[MX], child[MX], chainid[MX], chainpos[MX], head[MX], nchain; vii adj[MX]; ll upv[MX], dis[MX], ans; //vector<int>nodes[MX]; vector<ll> lt[MX], rt[MX]; vector<data> chain[MX]; void build_chain(int hd, int v) { upv[nchain] = v; /// sz[nchain] = 0; for(int k = 0, v = hd; v != -1; k++, v = child[v]) { rt[nchain].pb(dis[v] - dis[hd]); // nodes[nchain].pb(v); sz[nchain]++; chainid[v] = nchain; chainpos[v] = k; head[v] = hd; } lt[nchain].pb(0); for(int i = sz(rt[nchain]) - 2; i >= 0; i--) { lt[nchain].pb(lt[nchain].back() + rt[nchain][i + 1] - rt[nchain][i]); } reverse(all(lt[nchain])); chain[nchain].resize(4 * sz[nchain]); nchain++; return; } void dfs(int u) { weight[u] = 1; child[u] = -1; int mx = 0; repv(i, adj[u]) { int v = adj[u][i].xx; if(v != par[u]) { par[v] = u; dep[v] = dep[u] + 1; dis[v] = dis[u] + adj[u][i].yy; dfs(v); if(weight[v] > mx) { mx = weight[v]; child[u] = v; } weight[u] += weight[v]; } } repv(i,adj[u]) { int v = adj[u][i].xx; if(v != par[u] && v != child[u]) build_chain(v, adj[u][i].yy); } return; } void HLD(int u) { par[u] = -1; dfs(u); build_chain(u, 0); return; } data query(int chid, int idx, int st, int ed, int s, int e) { if(s > ed || e < st) return data(); if(st == s && ed == e) { return chain[chid][idx]; } data ret; if(e <= mid) ret = query(chid, lft, st, mid, s, e); else if(s > mid) ret = query(chid, rgt, mid + 1, ed, s, e); else { data A = query(chid, lft, st, mid, s, mid), B = query(chid, rgt, mid + 1, ed, mid + 1, e); ret.s = A.s + B.s; ret.n = A.n + B.n; ret.l = A.l + B.l; ret.r = A.r + B.r; } return ret; } void update(int chid, int idx, int st, int ed, int x, ll v, int t) { if(st == ed) { if(t) { chain[chid][idx].s += v; chain[chid][idx].n += 1; chain[chid][idx].l += lt[chid][x]; chain[chid][idx].r += rt[chid][x]; } else { chain[chid][idx].s -= v; chain[chid][idx].n -= 1; chain[chid][idx].l -= lt[chid][x]; chain[chid][idx].r -= rt[chid][x]; } return; } if(x <= mid) update(chid, lft, st, mid, x, v, t); else update(chid, rgt, mid + 1, ed, x, v, t); chain[chid][idx].s = chain[chid][lft].s + chain[chid][rgt].s; chain[chid][idx].n = chain[chid][lft].n + chain[chid][rgt].n; chain[chid][idx].l = chain[chid][lft].l + chain[chid][rgt].l; chain[chid][idx].r = chain[chid][lft].r + chain[chid][rgt].r; return; } void insert(int x, int t) { ll prevs, prevn, add; prevs = prevn = add = 0; while(x != -1) { int id = chainid[x], pos = chainpos[x]; if(t) { data tmp = query(id, 1, 0, sz[id] - 1, 0, pos); ans += tmp.s + tmp.l - lt[id][pos] * tmp.n - prevs + add * (tmp.n - prevn); tmp = query(id, 1, 0, sz[id] - 1, pos + 1, sz[id] - 1); ans += tmp.s + tmp.r - rt[id][pos] * tmp.n + add * tmp.n; } data tmp = chain[id][1]; update(id, 1, 0, sz[id] - 1, pos, add, t); prevs = tmp.s + tmp.r + tmp.n * upv[id]; prevn = tmp.n; add += dis[x] - dis[head[x]] + upv[id]; x = par[head[x]]; } return; } //ll dp[110][110]; int main() { // srand(time(0)); int m; scanf("%d%d", &n, &m); // rep(i, 1, n) { // rep(j, 1, n) { // if(i == j) dp[i][j] = 0; // else dp[i][j] = 1e9; // } // } rep(i, 1, n - 1) { int a, b, c; scanf("%d%d%d", &a, &b, &c); // dp[a][b] = min(dp[a][b], (ll)c); // dp[b][a] = min(dp[b][a], (ll)c); adj[a].pb(mp(b, c)); adj[b].pb(mp(a, c)); } // rep(k, 1, n) { // rep(i, 1, n) { // rep(j, 1, n) { // dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); // } // } // } HLD(1); // ///test // // cerr << nchain << endl; // rep(i, 0, nchain - 1) { // cerr << i <<": "; // repv(j, nodes[i]) { // cerr << nodes[i][j] << " "; // } // cerr << endl; // } // while(1) { // // int t = rand() % min(n, 2) + 1; // // vi vv; // // ans = 0; // rep(i, 0, t - 1) { // int x = rand() % n + 1; // vv.pb(x); // insert(x, 1); // } // // ll tans = 0; // repv(i, vv) { // repv(j, vv) { // if(j > i) { // tans += dp[vv[i]][vv[j]]; // } // } // } // // if(ans != tans) { // // cerr << "BAD" << endl; // // cerr << sz(vv) << endl; // repv(i, vv) { // cerr << vv[i] << " "; // } // cerr << endl; // cerr << ans << " " << tans << endl; // exit(0); // } // // repv(i, vv) { // insert(vv[i], 0); // } // } while(m--) { ans = 0; int t; scanf("%d", &t); vi vv; rep(i, 0, t - 1) { int x; scanf("%d", &x); vv.pb(x); insert(x, 1); } cout << ans << endl; repv(i, vv) { insert(vv[i], 0); } } return 0; }