#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> ii; /////////////////////////////////////////////////////// BEGIN OF HLD /////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////// Note: 0-indexed vertices ////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////////////////// class HLD { private: int current_index; void hld0(int v); void hld1(int v); public: std::vector<int> *adj; int *parent, *subtree_size, *special_child, *depth; int *head, *tail, *idx, *rev, *subtree_end, *relative_idx; HLD(int n); ~HLD(); void add_edge(int u, int v); void add_arc(int u, int v); void compute(); int lca(int u, int v); int dist(int u, int v); }; HLD::HLD(const int n) { adj = new vector<int>[n]; parent = new int[n]; subtree_size = new int[n]; special_child = new int[n]; depth = new int[n]; head = new int[n]; tail = new int[n]; idx = new int[n]; rev = new int[n]; subtree_end = new int[n]; relative_idx = new int[n]; } HLD::~HLD() { delete[] adj; delete[] parent; delete[] subtree_size; delete[] special_child; delete[] depth; delete[] head; delete[] tail; delete[] idx; delete[] rev; delete[] subtree_end; delete[] relative_idx; } void HLD::add_edge(const int u, const int v) { adj[u].push_back(v); adj[v].push_back(u); } void HLD::add_arc(const int u, const int v) { adj[u].push_back(v); } void HLD::compute() { parent[0] = -1; depth[0] = 0; hld0(0); current_index = 0; head[0] = 0; hld1(0); } void HLD::hld0(const int v) { subtree_size[v] = 1; special_child[v] = -1; for (int i = adj[v].size()-1; i >= 0; --i) { const int w = adj[v][i]; if (w == parent[v]) continue; depth[w] = 1 + depth[v]; parent[w] = v; hld0(w); subtree_size[v] += subtree_size[w]; } for (int i = adj[v].size()-1; i >= 0; --i) { const int w = adj[v][i]; if (w == parent[v]) continue; if (subtree_size[w] > subtree_size[v] / 2) special_child[v] = w; } } void HLD::hld1(const int v) { idx[v] = current_index; rev[current_index] = v; current_index += 1; relative_idx[v] = idx[v] - idx[head[v]]; if (special_child[v] == -1) { tail[v] = v; } else { head[special_child[v]] = head[v]; hld1(special_child[v]); tail[v] = tail[special_child[v]]; } for (int i = adj[v].size()-1; i >= 0; --i) { const int w = adj[v][i]; if (w == parent[v]) continue; if (w == special_child[v]) continue; head[w] = w; hld1(w); } subtree_end[v] = current_index - 1; } int HLD::lca(int u, int v) { while (head[u] != head[v]) { if (depth[head[u]] < depth[head[v]]) v = parent[head[v]]; else u = parent[head[u]]; } return depth[u] < depth[v] ? u : v; } int HLD::dist(const int u, const int v) { return depth[u] + depth[v] - 2*depth[lca(u, v)]; } /////////////////////////////////////////////////////// END OF HLD /////////////////////////////////////////////////////// const int MAX_N = 100000; int n; vector<ii> adj[MAX_N+1]; int special[MAX_N+1]; long long a[MAX_N+1]; long long c[MAX_N+1]; long long d[MAX_N+1]; void solve(const int u, const int v) { a[v] = 0; c[v] = special[v]; d[v] = 0; for (const ii x : adj[v]) { const int w = x.first; const int vw = x.second; if (w == u) continue; solve(v, w); a[v] += a[w]; c[v] += c[w]; d[v] += d[w]; d[v] += c[w] * vw; } for (const ii x : adj[v]) { const int w = x.first; const int vw = x.second; if (w == u) continue; a[v] += (d[w] + c[w]*vw) * (c[v] - c[w]); } //printf("a[%d] = %lld\n", v, a[v]); //printf("c[%d] = %lld\n", v, c[v]); //printf("d[%d] = %lld\n", v, d[v]); //puts(""); } int dr[MAX_N+1]; inline void precompute_distances(const int u, const int v) { for (const ii x : adj[v]) { const int w = x.first; const int vw = x.second; if (w == u) continue; dr[w] = dr[v] + vw; precompute_distances(v, w); } } const int MAX_X = MAX_N*2; int dfs_idx = 0; int num[MAX_X], depth[MAX_X], first_visit[MAX_N+1]; inline void precompute_lca(const int u, const int v, const int dpt) { num[dfs_idx] = v; depth[dfs_idx] = dpt; first_visit[v] = dfs_idx; dfs_idx += 1; for (const ii x : adj[v]) { const int w = x.first; //const int vw = x.second; if (w == u) continue; precompute_lca(v, w, dpt+1); num[dfs_idx] = v; depth[dfs_idx] = dpt; dfs_idx += 1; } } const int MAX_LOG = 17; int sparse[MAX_X][MAX_LOG+1]; inline void precompute_sparse() { dfs_idx = 0; precompute_lca(0, 1, 0); memset(sparse, -1, sizeof sparse); const int x = 2*n; for (int i = 0; i < x; ++i) sparse[i][0] = i; for (int j = 1; j <= MAX_LOG; ++j) { for (int i = 0; ; ++i) { int jj = j-1; if (i + (1<<j) - 1 >= x) break; int x1 = sparse[i][jj]; int x2 = sparse[i + (1<<jj)][jj]; if (depth[x1] < depth[x2]) sparse[i][j] = x1; else sparse[i][j] = x2; } } } int logs[MAX_X]; inline void precompute_logs() { const int x = 2*n; logs[1] = 0; for (int i = 2; i < x; ++i) logs[i] = 1 + logs[i>>1]; } inline int compute_lca(const int a, const int b) { int va = first_visit[a]; int vb = first_visit[b]; if (va > vb) swap(va, vb); int best_power = logs[vb-va+1]; int x1 = sparse[va][best_power]; int x2 = sparse[vb - (1<<best_power) + 1][best_power]; return depth[x1]<depth[x2] ? num[x1] : num[x2]; } inline int compute_distance(const int u, const int v) { const int lca = compute_lca(u, v); return dr[v] + dr[u] - 2*dr[lca]; } int main() { int t; scanf("%d%d", &n, &t); for (int i = 1; i < n; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } precompute_distances(0, 1); precompute_logs(); precompute_sparse(); int k; while(scanf("%d", &k) > 0) { //printf("Query!!!\n"); if (k == 1) { puts("0"); } else if (k == 2) { int u, v; scanf("%d%d", &u, &v); printf("%d\n", compute_distance(u, v)); } else { int v[k]; for (int i = 0; i < k; ++i) scanf("%d", v+i); if (k <= 500) { long long ans = 0; for (int i = 0; i < k; ++i) for (int j = i+1; j < k; ++j) ans += compute_distance(v[i], v[j]); printf("%lld\n", ans); } else { for (int i = 0; i < k; ++i) special[v[i]] += 1; solve(0, 1); printf("%lld\n", a[1]); for (int i = 0; i < k; ++i) special[v[i]] = 0; } } } }