/** * author: enot.1.10, Vladimir Smykalov (enot.1.10@gmail.com) * created: 19.09.2015 20:34:54 **/ #include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <ctime> #include <cassert> #include <queue> #define fs first #define sc second #define F first #define S second #define pb push_back #define mp make_pair #define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i) #define forit(it,v) for(typeof((v).begin()) it = v.begin() ; it != (v).end() ; ++it) #define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr) #define sz(a) ((int)(a).size()) #define all(a) (a).begin(),a.end() #define pw(x) (1LL<<(x)) using namespace std; typedef long long ll; typedef double dbl; typedef vector<int> vi; typedef pair<int, int> pi; const int inf = (int)1.01e9; const dbl eps = 1e-9; /* --- main part --- */ #define TASK "1" #define next sdlfkj const int maxn = (int)1e5 + 10; const int maxe = 2 * maxn; int head[maxn], next[maxe], to[maxe], len[maxe], ec = 1; inline void add(int x, int y, int l) { ec += 1; to[ec] = y; next[ec] = head[x]; head[x] = ec; len[ec] = l; } int st[2 * maxn], stc = 0; int dep[maxn]; ll sum[maxn]; const int LOG = 20; pi ST[LOG][2 * maxn]; int pos[maxn]; int loglog[2 * maxn]; int mark[maxn]; int cnt[maxn]; int X[maxn][3]; int XC = 0; inline int lca(int x, int y) { x = pos[x], y = pos[y]; if (x > y) swap(x, y); int l = loglog[y - x]; return min(ST[l][x], ST[l][y - (1 << l) + 1]).sc; } inline ll dist(int x, int y) { int z = lca(x, y); //eprintf("lca %d %d --> %d\n", x + 1, y + 1, z + 1); return sum[x] + sum[y] - 2 * sum[z]; } int ts[maxn], tsc = 0; void dfsInit(int x, int d, ll s) { mark[x] = 1; dep[x] = d; sum[x] = s; pos[x] = stc; st[stc++] = x; for (int e = head[x]; e; e = next[e]) { int y = to[e]; if (mark[y] == 0) { //E[x].pb(mp(y, len[e])); dfsInit(y, d + 1, s + len[e]); st[stc++] = x; X[XC][0] = x; X[XC][1] = y; X[XC][2] = len[e]; XC++; } } ts[tsc++] = x; } int n; void init() { dfsInit(0, 0, 0); forn(i, stc) ST[0][i] = mp(dep[st[i]], st[i]); for (int i = 1; i < LOG; ++i) for (int j = 0; j <= stc - (1 << i); ++j) { ST[i][j] = min(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]); } for (int i = 2; i < stc; ++i) loglog[i] = loglog[i >> 1] + 1; } ll RES = 0; ll CNT = 0; /*void dfs(int x) { mark[x] = 1; for (int e = head[x]; e; e = next[e]) { int y = to[e]; if (mark[y] == 0) { dfs(y); cnt[x] += cnt[y]; RES += cnt[y] * (ll)(CNT - cnt[y]) * len[e]; } } } */ ll calc() { RES = 0; /*forn(i, tsc) { int x = ts[i]; forn(j, sz(E[x])) { int y = E[x][j].fs; cnt[x] += cnt[y]; RES += cnt[y] * (ll)(CNT - cnt[y]) * E[x][j].sc; } } */ forn(i, XC) { cnt[X[i][0]] += cnt[X[i][1]]; RES += cnt[X[i][1]] * (ll)(CNT - cnt[X[i][1]]) * X[i][2]; } return RES; } const int maxv = (int)1e6 + 10; int v[maxv], vc = 0; const int SQRT = 300; int main() { #ifdef home assert(freopen(TASK".in", "r", stdin)); assert(freopen(TASK".out", "w", stdout)); #endif int q; scanf("%d%d", &n, &q); forn(i, n - 1) { int x, y, z; scanf("%d%d%d", &x, &y, &z); --x, --y; add(x, y, z); add(y, x, z); } init(); forn(_, q) { int k; scanf("%d", &k); forn(i, k) scanf("%d", &v[i]); forn(i, k) v[i] -= 1; if (k < SQRT) { ll res = 0; forn(i, k) forn(j, i) res += dist(v[i], v[j]); printf("%lld\n", res); } else { forn(i, n) cnt[i] = 0; forn(i, k) cnt[v[i]] += 1; CNT = k; ll res = calc(); printf("%lld\n", res); } } #ifdef home eprintf("Time: %d ms\n", (int)(clock() * 1000. / CLOCKS_PER_SEC)); #endif return 0; }