#include int ri() { int n; scanf("%d", &n); return n; } std::vector > > hen; std::vector alive; std::vector size; void dfs(int i, int prev) { size[i] = 1; for (auto j : hen[i]) if (j.first != prev && alive[j.first]) { dfs(j.first, i); size[i] += size[j.first]; } } int get_centroid(int i) { dfs(i, -1); while (1) { int max = 0; int maxindex = -1; for (auto j : hen[i]) if (alive[j.first] && size[j.first] < size[i] && max < size[j.first]) max = size[j.first], maxindex = j.first; if (max > size[i] / 2) i = maxindex; else break; } return i; } int64_t res = 0; std::vector > path_color; void centroid_rec(int i) { i = get_centroid(i); struct Info { std::vector > two_match; std::vector two_side; std::vector one; int one_num = 0; }; std::vector infos; for (auto j : hen[i]) { if (!alive[j.first]) continue; infos.push_back({}); Info &info = infos.back(); std::queue > que; path_color[j.first] = {j.second, -1}; que.push({j.first, i}); while (que.size()) { auto k = que.front(); auto &cur_color = path_color[k.first]; que.pop(); if (cur_color.second != -1) { if (cur_color.second < cur_color.first) std::swap(cur_color.first, cur_color.second); info.two_match.push_back(cur_color); info.two_side.push_back(cur_color.first); info.two_side.push_back(cur_color.second); } else { info.one_num++; info.one.push_back(cur_color.first); } for (auto l : hen[k.first]) if (l.first != k.second && alive[l.first]) { path_color[l.first] = cur_color; if (path_color[l.first].first != l.second) { if (path_color[l.first].second == -1) path_color[l.first].second = l.second; else if (path_color[l.first].second != l.second) continue; } que.push({l.first, k.first}); } } std::sort(info.two_match.begin(), info.two_match.end()); std::sort(info.two_side.begin(), info.two_side.end()); std::sort(info.one.begin(), info.one.end()); } Info all; for (auto &j : infos) { for (auto &k : j.two_match) all.two_match.push_back(k); for (auto &k : j.two_side) all.two_side.push_back(k); for (auto &k : j.one) all.one.push_back(k); all.one_num += j.one_num; } std::sort(all.two_match.begin(), all.two_match.end()); std::sort(all.two_side.begin(), all.two_side.end()); std::sort(all.one.begin(), all.one.end()); auto count_in = [&] (auto array, auto val) { return std::upper_bound(array.begin(), array.end(), val) - std::lower_bound(array.begin(), array.end(), val); }; auto calc = [&] (Info &target, Info &main) { int64_t res = 0; for (auto &j : main.two_match) { res += count_in(target.two_match, j); res += count_in(target.one, j.first) + count_in(target.one, j.second); } for (auto &j : main.one) { res += count_in(target.two_side, j); res += target.one_num - count_in(target.one, j); } return res; }; for (auto &j : infos) res += calc(all, j) - calc(j, j); res += all.two_match.size() * 2; alive[i] = false; for (auto &j : hen[i]) if (alive[j.first]) centroid_rec(j.first); } void run() { int n = hen.size(); alive.resize(n, true); size.resize(n); path_color.resize(n); centroid_rec(0); res /= 2; } int main() { int n = ri(); int k = ri(); hen.resize(n); for (int i = 1; i < n; i++) { int x = ri() - 1; int y = ri() - 1; int c = ri() - 1; hen[x].push_back({y, c}); hen[y].push_back({x, c}); } run(); printf("%" PRId64 "\n", res); return 0; }