#include <stdlib.h> #include <stdint.h> #include <string.h> #include <inttypes.h> #include <algorithm> struct tree_node { int sibling; int child; int nchild; int ctp; //cost to parent }N[100001]; int npid[100001]; int nc; struct tree_path { int parent, anchor; }P[100000]; struct tree_path2 { int child, sibling; }P2[100000]; struct tree_node2 { int count; int order; }N2[100001]; int psums[100000], psize[100000], pss[100000]; int psc; int pc; struct edge { int to; int next; int cost; }E[200000]; int head[100001], ec; static inline void add_edge(int x, int y, int cost) { E[ec].to = y; E[ec].next = head[x]; E[ec].cost = cost; head[x] = ec++; E[ec].to = x; E[ec].next = head[y]; E[ec].cost = cost; head[y] = ec++; } static inline void build_tree(int root, int parent) { int i = head[root]; if (i != -1 && E[i].to == parent) i = E[i].next; if (i == -1) { N[root].nchild = 0; return; } int now = E[i].to; N[root].child = now; N[root].nchild = 1; build_tree(now, root); N[now].ctp = E[i].cost; while((i = E[i].next) != -1) { if (E[i].to == parent) continue; N[now].sibling = E[i].to; now = E[i].to; build_tree(now, root); N[now].ctp = E[i].cost; N[root].nchild++; } N[now].sibling = -1; } static inline void _partition_tree(int root) { int now = root; int mypc = pc++; int nowchild = -1; int id = 1; npid[root] = mypc; N2[root].order = 0; while(N[now].nchild > 0) { int tmp = N[now].child; int max = -1, d; while(tmp != -1) { if (N[tmp].nchild > max) { max = N[tmp].nchild; d = tmp; } tmp = N[tmp].sibling; } N2[d].order = id++; npid[d] = mypc; tmp = N[now].child; while(tmp != -1) { if (tmp != d) { _partition_tree(tmp); int k = npid[tmp]; P[k].parent = mypc; P[k].anchor = now; nowchild = k; } tmp = N[tmp].sibling; } now = d; } pss[mypc] = psc; psc += id; psize[mypc] = id; } static inline void partition_tree(int root) { int rootpc = pc; _partition_tree(root); P[rootpc].parent = -1; for(int i = 1; i <= nc; i++) { int pnode = npid[i]; int order = N2[i].order; psums[pss[pnode]+order] = N[i].ctp; } for(int i = 0; i < pc; i++) for(unsigned int j = pss[i]+1; j < pss[i]+psize[i]; j++) psums[j] += psums[j-1]; } #define unlikely(x) (__builtin_expect(!!(x), 0)) #define likely(x) (__builtin_expect(!!(x), 1)) int marked_path[100000], nmarked_path; int path_map[100000]; int panchor[100000], ac; int degree[100000]; int nas[100001]; //start index of path node anchor int nac[100001]; //number of path node anchor int ancsum[100000]; int aop[100000]; static inline void do_node(int node, int c) { int now = npid[node]; ancsum[now] += c; if (N2[node].count) { N2[node].count += c; return; } if (path_map[now] < 0) { path_map[now] = nmarked_path; marked_path[nmarked_path++] = now; nac[nmarked_path]++; } else nac[path_map[now]+1]++; N2[node].count = c; panchor[ac++] = node; int parent = P[now].parent; if (parent > 0) degree[parent]++; } static inline int pdfs(int root) { int ptr = P2[root].child; int sum = ancsum[root]; ancsum[root] = 0; while(ptr != -1) { int anchor = P[ptr].anchor; if (!N2[anchor].count) { panchor[ac++] = anchor; nac[path_map[root]+1]++; } int tmp = pdfs(ptr); sum += tmp; N2[anchor].count += tmp; ptr = P2[ptr].sibling; } P2[root].child = -1; return sum; } static inline void collect_anchors() { int h = 0; while(h != nmarked_path) { int cur = marked_path[h]; int parent = P[cur].parent; if (parent < 0) { h++; continue; } P2[cur].sibling = P2[parent].child; P2[parent].child = cur; if (path_map[parent] >= 0) { h++; continue; } path_map[parent] = nmarked_path; marked_path[nmarked_path++] = parent; h++; } pdfs(0); for(int i = 1; i <= nmarked_path; i++) nac[i] += nac[i-1]; memcpy(nas, nac, sizeof(int)*(nmarked_path+1)); for(int i = 0; i < ac; i++) { int pid = path_map[npid[panchor[i]]]; aop[nac[pid]++] = panchor[i]; } memset(nac, 0, sizeof(int)*(nmarked_path+1)); } static inline uint64_t do_path_node(uint64_t total) { uint64_t ans = 0; int first = nas[nmarked_path], last = 0; for(int xnode = nmarked_path-1; xnode >= 0; xnode--) { last = first-1; first = nas[xnode]; int node = marked_path[xnode]; if (last == first) { uint64_t tmp = N2[aop[last]].count; N2[aop[last]].count = 0; if (tmp == total) continue; uint64_t tmp2 = tmp*(total-tmp); ans += psums[pss[node]+N2[aop[first]].order]*tmp2; continue; } //qsort(aop+first, last-first+1, sizeof(int), cmp); std::sort(&aop[first], &aop[last+1], [](int &a, int &b){ return N2[a].order < N2[b].order; }); uint64_t tmp = N2[aop[last]].count; N2[aop[last]].count = 0; uint64_t tmp2 = tmp*(total-tmp); int last_order = N2[aop[last]].order; for(int i = last-1; i >= first; i--) { int this_order = N2[aop[i]].order; uint64_t cost = psums[pss[node]+last_order]-psums[pss[node]+this_order]; uint64_t delta = N2[aop[i]].count; N2[aop[i]].count = 0; last_order = this_order; tmp2 = tmp*(total-tmp); ans += cost*tmp2; tmp += delta; } tmp2 = tmp*(total-tmp); ans += psums[pss[node]+N2[aop[first]].order]*tmp2; } return ans; } int mark_count[100001]; int marked_node[100000], nmarked_node; static inline void mark_node(int node) { if (likely(mark_count[node] == 0)) { mark_count[node] = 1; marked_node[nmarked_node++] = node; } else mark_count[node]++; } static inline void clear() { //for(int i = 0; i < ac; i++) // pcount[panchor[i]] = 0; //for(int j = 0; j < nmarked_node; j++) // mark_count[marked_node[j]] = 0; ac = 0; nmarked_node = 0; for(int j = 0; j < nmarked_path; j++) path_map[marked_path[j]] = -1; nmarked_path = 0; } static inline int in_num(void) { char tmp = getchar(); while(tmp < '0' || tmp > '9') tmp = getchar(); int ans = 0; do { ans = ans*10+tmp-'0'; tmp = getchar(); } while (tmp <= '9' && tmp >= '0'); return ans; } char buf[30]; static inline void out_num(uint64_t o) { buf[29]=0; int i = 28; while(o>0) { buf[i] = o%10+'0'; o/=10; i--; } puts(buf+i+1); } int main() { memset(path_map, 255, sizeof(path_map)); memset(P2, 255, sizeof(P2)); int n, m; n = in_num(); m = in_num(); memset(head, 255, sizeof(head)); for(int i = 0; i<n-1; i++) { int a, b, c; a = in_num(); b = in_num(); c = in_num(); //scanf("%d%d%d", &a, &b, &c); add_edge(a, b, c); } nc = n; build_tree(1, -1); N[1].ctp = 0; partition_tree(1); //printf("%d\n", pc); for(int i = 0; i<m; i++) { clear(); int k; k = in_num(); for(int j = 0; j<k; j++) { int tmp = in_num(); mark_node(tmp); } for(int j = 0; j < nmarked_node; j++) { int tmp = mark_count[marked_node[j]]; mark_count[marked_node[j]] = 0; do_node(marked_node[j], tmp); } collect_anchors(); uint64_t ans = 0; //cerr << nmarked_path << "\n"; out_num(do_path_node(k)); //printf("%" PRIi64 "\n", do_path_node(k)); } return 0; }