题目链接:https://codeforces.com/contest/1156/problem/D

题解:可以这样想,对于答案要求的pair数,(x,y)(x, y)要么xxyy全1,要么全0,要么先1后全0,那么用并查集维护两种不同边的森林即可。

#include <bits/stdc++.h>
#define pa pair<ll, ll>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

const ll INF = 0x3f3f3f3f;
const ll N = 2e5 + 5;
struct edge {
    ll u,v,p;
}e[N];
ll n,f[N][2],sum[N][2];
ll find(ll x, ll c) {
    return x == f[x][c] ? f[x][c] : f[x][c] = find(f[x][c], c);
}
ll merge(ll u, ll v, ll c) {
    u = find(u, c);
    v = find(v, c);
    if(u != v) {
        f[v][c] = u;
        sum[u][c] += sum[v][c];
    }
}
int main() {
#ifdef INCTRY
    freopen("input.txt", "rt", stdin);
#endif
    read(n);
    for(ll i = 1; i <= n - 1; i++) {
        read(e[i].u); read(e[i].v); read(e[i].p);
        f[i][0] = f[i][1] = i; sum[i][0] = sum[i][1] = 1;
    }
    f[n][0] = f[n][1] = n;
    sum[n][0] = sum[n][1] = 1;
    ll ans = 0;
    for(ll i = 1; i <= n - 1; i++) {
        merge(e[i].u, e[i].v, e[i].p);
    }   
    for(ll i = 1; i <= n; i++) {
        if(f[i][0] == i)
            ans += sum[i][0] * (sum[i][0] - 1);
        if(f[i][1] == i)
            ans += sum[i][1] * (sum[i][1] - 1);
        
        ans += (sum[find(i, 0)][0] - 1) * (sum[find(i, 1)][1] - 1);
    }
    cout << ans;
#ifdef INCTRY
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}