#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; using ll = long long; #define rep(i,n) for(int i=0;i> n; vector>> g(n); rep(i, n - 1) { int a, b, c; cin >> a >> b >> c; --a, --b; g[a].emplace_back(b, c); g[b].emplace_back(a, c); } vector siz(n, 1), x(n); auto dfs0 = [&](auto&& f, int cur, int par)->void { int par_idx = -1; rep(i, g[cur].size()) { auto [to, weight] = g[cur][i]; if (to == par) { par_idx = i; continue; } x[to] = x[cur] ^ weight; f(f, to, cur); siz[cur] += siz[to]; } if (par_idx != -1) { swap(g[cur][par_idx], g[cur].back()); g[cur].pop_back(); } }; dfs0(dfs0, 0, -1); auto sorted_x = x; sort(sorted_x.begin(), sorted_x.end()); sorted_x.erase(unique(sorted_x.begin(), sorted_x.end()), sorted_x.end()); rep(i, n)x[i] = lower_bound(sorted_x.begin(), sorted_x.end(), x[i]) - sorted_x.begin();//compress vector y_sum(sorted_x.size()), cnt_sum(sorted_x.size()); vector y(n, -1), cnt(n, -1); ll ans = ll(n) * (n - 1); int parity[2] = { 1,-1 }; auto dfs1 = [&](auto&& f, int cur, bool type)->void { y_sum[x[cur]] += parity[type] * y[cur]; cnt_sum[x[cur]] += parity[type] * cnt[cur]; for (int i = 0; i < g[cur].size(); ++i) { f(f, g[cur][i].first, type); } }; auto dfs2 = [&](auto&& f, int cur, int par, bool type)->void { sort(g[cur].begin(), g[cur].end(), [&](const pair& i, const pair& j) {return siz[i.first] > siz[j.first]; }); for (int i = 1; i < g[cur].size(); ++i) { f(f, g[cur][i].first, cur, true); } if (!g[cur].empty())f(f, g[cur][0].first, cur, false); for (int i = 1; i < g[cur].size(); ++i) { dfs1(dfs1, g[cur][i].first, false); } if (y[cur] == -1) { y[cur] = siz[cur] - y_sum[x[cur]]; cnt[cur] = 1 - cnt_sum[x[cur]]; } ans -= y_sum[x[cur]];//case-1 y_sum[x[cur]] += y[cur]; cnt_sum[x[cur]] += cnt[cur]; if (cur == 0) { rep(i, sorted_x.size())if (i != x[cur]) { ans -= ll(y_sum[i]) * cnt_sum[i];//case-3 } } else { ans -= ll(cnt_sum[x[par]]) * (n - siz[cur]);//case-2 ans -= ll(y_sum[x[par]]) * cnt_sum[x[par]];//case-3 ans += siz[cur];//case-3 } if (type) { for (int i = 0; i < g[cur].size(); ++i) { dfs1(dfs1, g[cur][i].first, true); } y_sum[x[cur]] -= y[cur]; cnt_sum[x[cur]] -= cnt[cur]; } }; dfs2(dfs2, 0, -1, false); cout << ans << "\n"; return 0; }