#include #include #include #include #include #include namespace nono { template struct EdgeBase { int from; int to; T weight; EdgeBase() {} EdgeBase(int from, int to, T weight = 1): from(from), to(to), weight(weight) {} }; using Edge = EdgeBase; template using WeightedEdge = EdgeBase; template class Graph { struct Edge_ { int to; T weight; int id; }; using iterator = std::vector::iterator; using const_iterator = std::vector::const_iterator; using subrange = std::ranges::subrange; using const_subrange = std::ranges::subrange; public: template friend Graph to_undirected_graph(int n, const std::vector>& edges); template friend Graph to_directed_graph(int n, const std::vector>& edges); subrange operator[](int i) { return std::ranges::subrange(edges_.begin() + indptr_[i], edges_.begin() + indptr_[i + 1]); } const_subrange operator[](int i) const { return std::ranges::subrange(edges_.begin() + indptr_[i], edges_.begin() + indptr_[i + 1]); } int size() const { return n_; } bool is_directed() const { return directed_; } bool is_undirected() const { return !is_directed(); } private: Graph(int n, const std::vector>& edges, bool directed) : n_(n), indptr_(n_ + 1), edges_(directed ? edges.size() : 2 * edges.size()), directed_(directed) { for (const auto& e: edges) { indptr_[e.from + 1]++; if (!directed_) indptr_[e.to + 1]++; } for (int i = 0; i < n_; i++) { indptr_[i + 1] += indptr_[i]; } auto index = indptr_; for (int i = 0; i < std::ssize(edges); i++) { const auto& e = edges[i]; edges_[index[e.from]++] = Edge_(e.to, e.weight, i); if (!directed_) edges_[index[e.to]++] = Edge_(e.from, e.weight, i); } } int n_; std::vector indptr_; std::vector edges_; bool directed_; }; template Graph to_undirected_graph(int n, const std::vector>& edges) { return Graph(n, edges, false); } template Graph to_directed_graph(int n, const std::vector>& edges) { return Graph(n, edges, true); } } // namespace nono #include #include #include namespace nono { template bool is_tree(const Graph& graph) { if (graph.is_directed()) return false; constexpr int NONE = -1; int n = graph.size(); std::vector used(n); auto dfs = [&](auto self, int u, int eid) -> bool { used[u] = 1; for (const auto& e: graph[u]) { if (e.id == eid) continue; if (used[e.to]) return false; if (!self(self, e.to, e.id)) return false; } return true; }; if (!dfs(dfs, 0, NONE)) return false; return std::ranges::all_of(used, [](int f) { return f == 1; }); } } // namespace nono namespace nono { template std::vector centroids(const Graph& graph) { int n = graph.size(); std::vector subtree(n); std::vector removed(n); std::vector result; result.reserve(n); auto calc_subtree = [&](auto&& self, int u, int p) -> int { subtree[u] = 1; for (const auto& e: graph[u]) { if (e.to == p || removed[e.to]) continue; subtree[u] += self(self, e.to, u); } return subtree[u]; }; std::vector cur; cur.push_back(0); while (!cur.empty()) { std::vector next; for (auto root: cur) { calc_subtree(calc_subtree, root, root); int centroid = root; bool flag = true; while (flag) { flag = false; for (const auto& e: graph[centroid]) { if (removed[e.to] || subtree[e.to] > subtree[centroid]) continue; if (subtree[root] <= 2 * subtree[e.to]) { centroid = e.to; flag = true; } } } result.push_back(centroid); removed[centroid] = true; for (const auto& e: graph[centroid]) { if (removed[e.to]) continue; next.push_back(e.to); } } cur = std::move(next); } return result; } } // namespace nono namespace nono { void solve() { int n, k; std::cin >> n >> k; std::vector> edges; edges.reserve(n - 1); for (int i = 0; i + 1 < n; i++) { int u, v, c; std::cin >> u >> v >> c; u--; v--; edges.emplace_back(u, v, c); } const auto graph = to_undirected_graph(n, edges); std::vector removed(n); long long ans = 0; for (auto centroid: centroids(graph)) { std::map, int> a; std::map b; std::map c; int d = 0; std::vector> path; auto dfs = [&](auto&& self, int u, int p, std::pair color) -> void { path.push_back(color); for (const auto& e: graph[u]) { if (e.to == p || removed[e.to]) continue; auto new_color = color; if (new_color.first == -1) { new_color.first = e.weight; self(self, e.to, u, new_color); } else if (new_color.first != e.weight && new_color.second == -1) { new_color.second = e.weight; self(self, e.to, u, new_color); } else if (new_color.first == e.weight || new_color.second == e.weight) { self(self, e.to, u, new_color); } } }; for (const auto& e: graph[centroid]) { if (removed[e.to]) continue; path.clear(); dfs(dfs, e.to, centroid, {e.weight, -1}); for (auto [c1, c2]: path) { if (c1 == -1) continue; if (c2 == -1) { ans += b[c1]; ans += d - c[c1]; } else { if (c1 > c2) std::swap(c1, c2); ans += a[std::pair(c1, c2)]; ans += c[c1]; ans += c[c2]; ans++; } } for (auto [c1, c2]: path) { if (c1 == -1) continue; if (c2 == -1) { c[c1]++; d++; } else { if (c1 > c2) std::swap(c1, c2); a[std::pair(c1, c2)]++; b[c1]++; b[c2]++; } } } removed[centroid] = true; } std::cout << ans << '\n'; } } // namespace nono int main() { std::cin.tie(0)->sync_with_stdio(0); nono::solve(); }