#include <iostream> #include <vector> #include <set> #include <map> #include <stack> #include <algorithm> struct node { int parent; int depth; uint64_t distance; }; struct meta { int v; uint64_t sum_c; uint64_t sum_cd; }; struct build_tree { const std::vector<std::vector<std::pair<int, int>>> &adjacency; std::vector<node> &tree; build_tree(const std::vector<std::vector<std::pair<int, int>>> &a, std::vector<node> &t) : adjacency{a}, tree{t} {} void operator()(int v) { for (const auto &entry : adjacency[v]) { int w = entry.first; if (tree[v].parent == w) continue; uint64_t c = entry.second; tree[w].parent = v; tree[w].depth = tree[v].depth+1; tree[w].distance = c; (*this)(w); } } }; struct comparator { const std::vector<node> &tree; comparator(const std::vector<node> &t) : tree{t} {} bool operator() (int lhs, int rhs) const { if (tree[lhs].depth == tree[rhs].depth) return lhs < rhs; else return tree[lhs].depth > tree[rhs].depth; } }; void read_tree(int N, std::vector<node> &tree) { std::vector<std::vector<std::pair<int, int>>> adjacency; adjacency.resize(N); tree.resize(N); for (int i = 0; i < N-1; i++) { int a, b, c; std::cin >> a >> b >> c; adjacency[a-1].push_back({b-1, c}); adjacency[b-1].push_back({a-1, c}); } int root = 0; tree[root].parent = -1; tree[root].depth = 1; tree[root].distance = 0; build_tree(adjacency, tree)(root); } int main() { int N, T; std::cin >> N >> T; std::vector<node> tree; read_tree(N, tree); // reuse index (with trash) std::vector<int> index; index.resize(N, 0); // 0 is root! for (int i = 0; i < T; i++) { int K; std::cin >> K; std::map<int, uint64_t> districts; for (int j = 0; j < K; j++) { int x; std::cin >> x; districts[x-1]++; } uint64_t result = 0; std::map<int, std::vector<meta>, std::greater<int>> unions; for (const auto &entry : districts) { unions[tree[entry.first].depth].push_back({entry.first, entry.second, 0}); } auto it = unions.begin(); std::vector<meta> level = std::move(it->second); std::vector<meta> new_level; unions.erase(it); while (!unions.empty() || level.size() > 1) { for (auto &n : level) { n.sum_cd += n.sum_c * tree[n.v].distance; n.v = tree[n.v].parent; // check index int idx = index[n.v]; if (idx < new_level.size() && new_level[idx].v == n.v) { auto &m = new_level[idx]; result += m.sum_c*n.sum_cd + m.sum_cd*n.sum_c; m.sum_c += n.sum_c; m.sum_cd += n.sum_cd; } else { index[n.v] = new_level.size(); new_level.push_back(n); } } it = unions.begin(); if (!unions.empty() && tree[new_level.front().v].depth == it->first) { for (auto &n : it->second) { // check index int idx = index[n.v]; if (idx < new_level.size() && new_level[idx].v == n.v) { auto &m = new_level[idx]; result += m.sum_c*n.sum_cd + m.sum_cd*n.sum_c; m.sum_c += n.sum_c; m.sum_cd += n.sum_cd; } else { // don't update index ... new_level.push_back(n); } } unions.erase(it); } std::swap(level, new_level); new_level.clear(); } std::cout << result << std::endl; } return 0; }