比赛 |
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;
}