#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <string.h> using namespace std; typedef long long lld; struct RangeMinimumQuery { int RMQ[300002][25], pw[21], getpow[300002]; int CMP(int a, int b) { if (a < b) return a; return b; } void Initialize(int n, int arr[]) { int i, j; int stp; pw[0] = 1; for (i=1; i<25; i++) { pw[i] = pw[i-1]*2; } getpow[0] = 0; stp = 0; for (i=1; i<300002; i++) { if (pw[stp+1] < i) stp++; getpow[i] = stp; } for (i=1; i<=n; i++) { RMQ[i][0] = arr[i]; } for (i=1; pw[i]<=n; i++) { for (j=1; j+pw[i]-1<=n; j++) { RMQ[j][i] = CMP(RMQ[j][i-1], RMQ[j+pw[i-1]][i-1]); } } } int GetMin(int from, int to) { if (from > to) swap(from, to); int stp = getpow[to-from+1]; return CMP(RMQ[from][stp], RMQ[to-pw[stp]+1][stp]); } } rmq; struct VRTX { int vert, dist; }; VRTX GetVert(int vert, int dist) { VRTX ret; ret.vert = vert; ret.dist = dist; return ret; } bool SH_ByName(VRTX a, VRTX b) { return (a.vert < b.vert); } int n, tests; vector<VRTX> inp[100002], graph[100002], compressed[100002]; int name[100002], real[100002], ffree; pair<int, int> cover[100002]; bool TFO[100002]; int vabove_val[100002]; int curs[1000002], csz, special[100002]; int org_set[1000002]; int KEY, sig_sp[100002]; int visit[100002], vsz, firstvisit[100002]; int pathdist[100002]; void Input() { scanf("%d %d", &n, &tests); for (int i=1; i<n; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); inp[a].push_back(GetVert(b, c)); inp[b].push_back(GetVert(a, c)); } } lld ans, cans = 0; void RollBack() { cans = 0; ans = 0; ffree = 1; KEY++; } void DFS_GiveName(int vert, int dist) { TFO[vert] = true; visit[++vsz] = ffree; if (firstvisit[ffree] == 0) firstvisit[ffree] = vsz; pathdist[ffree] = dist; name[vert] = ffree; real[ffree] = vert; ffree++; for (int i=0; i<inp[vert].size(); i++) { if (TFO[inp[vert][i].vert]) continue; DFS_GiveName(inp[vert][i].vert, dist+inp[vert][i].dist); visit[++vsz] = name[vert]; } cover[name[vert]] = make_pair(name[vert], ffree-1); } void MakeRoot(int nroot) { memset(TFO, 0, sizeof(TFO)); vsz = 0; DFS_GiveName(nroot, 0); rmq.Initialize(vsz, visit); for (int i=1; i<=n; i++) { int v1 = name[i]; for (int j=0; j<inp[i].size(); j++) { int v2 = name[inp[i][j].vert]; graph[ v1 ].push_back( GetVert(v2, inp[i][j].dist) ); } sort(graph[name[i]].begin(), graph[name[i]].end(), SH_ByName); } } int LCA(int vert1, int vert2) { return (rmq.GetMin(firstvisit[vert1], firstvisit[vert2])); } void UPD_SP(int ind) { if (sig_sp[ind] != KEY) { sig_sp[ind] = KEY; special[ind] = 0; } } void UpdateSpecials() { for (int i=1; i<=csz; i++) { curs[i] = name[org_set[i]]; UPD_SP(curs[i]); special[curs[i]]++; } sort(curs+1, curs+csz+1); } lld GetNewValue(lld oldans, int dist, int oldspeccnt, int newc) { return (oldans - (lld)dist*(lld)oldspeccnt + (lld)dist*(lld)newc); } int sUTFO[100002], sTFOkey; int scnt[100002], sv_scnt[100002]; int FillCounter(int vert) { sUTFO[vert] = sTFOkey; UPD_SP(vert); scnt[vert] = special[vert]; for (int i=0; i<compressed[vert].size(); i++) { if (sUTFO[compressed[vert][i].vert] == sTFOkey) continue; scnt[vert] += FillCounter(compressed[vert][i].vert); } sv_scnt[vert] = scnt[vert]; return scnt[vert]; } int ansfor[100002]; void DFS_Solution(int curroot, lld curans) { sUTFO[curroot] = sTFOkey; UPD_SP(curroot); ans += curans*special[curroot]; int allcnt=csz; for (int i=0; i<compressed[curroot].size(); i++) { if (sUTFO[compressed[curroot][i].vert] == sTFOkey) continue; if (sv_scnt[compressed[curroot][i].vert] == 0) continue; int nroot = compressed[curroot][i].vert; int sv = vabove_val[nroot]; int sva = scnt[nroot]; int svb = vabove_val[curroot]; scnt[curroot] = csz - scnt[nroot]; scnt[nroot] = csz; vabove_val[nroot] = allcnt-vabove_val[nroot]; vabove_val[curroot] = vabove_val[nroot]; lld nans = GetNewValue(curans, compressed[curroot][i].dist, sv, scnt[curroot]); DFS_Solution(nroot, nans); vabove_val[nroot] = sv; vabove_val[curroot] = svb; scnt[curroot] = csz; scnt[nroot] = sva; } } int imp[100002], isz; int important[100002], ikey; int GetLast_SmallerOrEqual(int than, int from, int to) { int bl = from, br = to, bmid, bres=-1; while (bl <= br) { bmid = (bl+br)/2; if (imp[bmid] <= than) { bres = bmid; bl = bmid+1; } else { br = bmid-1; } } return bres; } int GetDist(int vert1, int vert2) { int lca = LCA(vert1, vert2); return (pathdist[vert1]+pathdist[vert2]-2*pathdist[lca]); } int tozero[100002], tzs; int Compress(int from, int to) { int parent = LCA(imp[from], imp[to]); int curbeg = from; if (important[parent] == ikey) curbeg++; for (int i=0; i<graph[parent].size(); i++) { int nvert = graph[parent][i].vert; if (nvert < parent) continue; int curend = GetLast_SmallerOrEqual(cover[nvert].second, curbeg, to); if (curend == -1) continue; int root = Compress(curbeg, curend); compressed[parent].push_back( GetVert(root, GetDist(parent, root)) ); compressed[root].push_back( GetVert(parent, GetDist(parent, root)) ); curbeg = curend+1; } tozero[++tzs] = parent; return parent; } void ProcessSet() { RollBack(); scanf("%d", &csz); for (int i=1; i<=csz; i++) { scanf("%d", &org_set[i]); } UpdateSpecials(); for (int i=1; i<=tzs; i++) { compressed[tozero[i]].clear(); } tzs = 0; isz=0; ikey++; for (int i=1; i<=csz; i++) { important[curs[i]] = ikey; imp[++isz] = curs[i]; } if (important[1] != ikey) { important[1] = ikey; imp[++isz] = 1; } sort(imp+1, imp+isz+1); int root = Compress(1, isz); sTFOkey++; FillCounter(1); sTFOkey++; for (int tm=1; tm<=tzs; tm++) { int i = tozero[tm]; if (sUTFO[i] == sTFOkey) continue; sUTFO[i] = sTFOkey; for (int j=0; j<compressed[i].size(); j++) { if (compressed[i][j].vert < i) continue; vabove_val[compressed[i][j].vert] = scnt[compressed[i][j].vert]; cans += vabove_val[compressed[i][j].vert]*compressed[i][j].dist; } } sTFOkey++; DFS_Solution(1, cans); printf("%lld\n", ans/2LL); } int main () { //freopen("input.txt", "r", stdin); Input(); RollBack(); MakeRoot(1); for (int t=1; t<=tests; t++) { ProcessSet(); } }