比赛 2025.6.2 评测结果 AAAAAAAAAA
题目名称 0-1-Tree 最终得分 100
用户昵称 wdsjl 运行时间 0.767 s
代码语言 C++ 内存使用 16.39 MiB
提交时间 2025-06-02 11:42:35
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

const int N = 2e5+10;

int n,ans,f[N][4]; 
vector <pii> G[N];

void dfs(int x, int fa) {
    for(int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i].first, z = G[x][i].second;
        if(y == fa) {
            continue;
        }
        dfs(y, x);
        if(z) {
            ans += 2 * (f[y][1] + 1) * (f[x][1] + 1);
            ans += (f[y][0] + f[y][2]) * (f[x][1] + 1);
            ans += (f[x][0] + f[x][2]) * (f[y][1] + 1);
            f[x][1] += f[y][1] + 1;
            f[x][2] += f[y][2] + f[y][0];
        } else {
            ans += 2 * (f[y][0] + 1) * (f[x][0] + 1);
            ans += (f[y][1] + f[y][3]) * (f[x][0] + 1);
            ans += (f[x][1] + f[x][3]) * (f[y][0] + 1);
            f[x][0] += f[y][0] + 1;
            f[x][3] += f[y][3] + f[y][1];
        }
    }
}

void solve() {
    
}

signed main(){
	freopen("0-1-Tree.in","r",stdin);
	freopen("0-1-Tree.out","w",stdout);
	scanf("%lld",&n);
    for(int i = 1; i < n; ++i) {
        int x, y, z;
        scanf("%lld%lld%lld",&x,&y,&z);
        G[x].push_back(make_pair(y, z));
        G[y].push_back(make_pair(x, z));
    }	
    dfs(1, 0);
    printf("%lld",ans);
	return 0;
}