#include <iostream> #include <algorithm> #include <string> #include <vector> #include <functional> using MainReturnInt = int; namespace io { #define DEFAULT_ISTREAM std::istream& stream = std::cin template<typename T> T Read(DEFAULT_ISTREAM) { T t; stream >> t; return t; } template<typename T> void Write(const T& t, std::ostream& stream = std::cout) { stream << t; } template<typename T> std::vector<T> ReadVector(int n, std::function<T(std::istream&)> f = Read<T>, DEFAULT_ISTREAM){ std::vector<T> v; v.reserve(n); std::generate(v.begin(), v.end(), std::bind(f, std::ref(stream))); return v; } } // namespace io #include <bits/stdc++.h> using namespace std; #define int long long const int MX = 100 * 1000 + 1; int gAnswer[MX]; struct TaskCitizenGroup { TaskCitizenGroup(): length_sum_(0), count_(0) {} int GetCount() const { return count_; } int GetLengthSum(int global_added) { return global_added + length_sum_; } void Normalize(int global_added) { length_sum_ += global_added * count_; } void ExtendAndUpdateAnswers(const TaskCitizenGroup& other, int global_added_here, int task_number) { gAnswer[task_number] += count_ * other.length_sum_ + other.count_ * ((count_ * global_added_here) +length_sum_); length_sum_ += other.length_sum_ - (global_added_here * other.count_); count_ += other.count_; } int length_sum_; int count_; }; struct NodeInfo { int global_added_to_lengths_; unordered_map<int, TaskCitizenGroup> tasks_; void Extend(NodeInfo& other) { for (auto& key_value : other.tasks_) { key_value.second.Normalize(other.global_added_to_lengths_); tasks_[key_value.first].ExtendAndUpdateAnswers(key_value.second, global_added_to_lengths_, key_value.first); } } }; using Edge = pair<int,int>; #define to first #define cost second int gVerticesCount, gTaskCount; vector<Edge> gGraph[MX]; NodeInfo gNodeInfo[MX]; void Dfs(int v, int p) { for (auto i : gGraph[v]) if (i.to != p) Dfs(i.to, v); vector<NodeInfo> son_node_infos; for (auto i: gGraph[v]) if(i.to != p) { gNodeInfo[i.to].global_added_to_lengths_ += i.cost; son_node_infos.emplace_back(move(gNodeInfo[i.to])); } if (son_node_infos.empty()) return; auto iterMax = max_element(son_node_infos.begin(), son_node_infos.end(), [](const NodeInfo& a, const NodeInfo& b) {return a.tasks_.size() < b.tasks_.size();}); swap(*iterMax, gNodeInfo[v]); for (auto& node_info: son_node_infos) { gNodeInfo[v].Extend(node_info); } } void ReadInput() { gVerticesCount = io::Read<int>(); gTaskCount = io::Read<int>(); for (int i = 0; i < gVerticesCount - 1; i++) { int a = io::Read<int>(), b = io::Read<int>(), cost = io::Read<int>(); gGraph[a].push_back({b, cost}); gGraph[b].push_back({a, cost}); } for(int i = 0; i < gTaskCount; i++) { int num_residents = io::Read<int>(); while(num_residents--) { gNodeInfo[io::Read<int>()].tasks_[i].count_ += 1; } } } MainReturnInt main() { ReadInput(); Dfs(1, 0); for (int i = 0; i < gTaskCount; i++) cout << gAnswer[i] << "\n"; }