C++14(g++5.4) 解法, 执行用时: 17ms, 内存消耗: 12504K, 提交时间: 2020-08-19 12:02:18

#include<bits/stdc++.h>
using namespace std;
int n;
long long cnt[2];
struct node{
	int v,w;
	node(int vv,int ww):v(vv),w(ww){}
};
vector<node>g[500010];
void dfs(int u,int fa,int val){
	cnt[val]++;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].v,w=g[u][i].w;
		if(v==fa){
			continue;
		}
		dfs(v,u,(val+w)%2);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1,x,y,z;i<n;i++){
		cin>>x>>y>>z;
		g[x].push_back(node(y,z));
		g[y].push_back(node(x,z));
	}
	dfs(1,-1,0);
	cout<<cnt[0]*cnt[0]*cnt[0]+cnt[1]*cnt[1]*cnt[1];
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 13ms, 内存消耗: 1248K, 提交时间: 2020-02-27 18:36:10

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,i,s,e,d,x=0,y=0;
vector<pair<ll,ll> >a[10005];
void dfs(ll m,ll q,ll l)
{
	if(l%2) y++;
	else x++;
	for(auto it:a[m])
	if(it.first!=q)
	dfs(it.first,m,(l+it.second)%2);
}
int main()
{
	cin>>n;
	for(i=1;i<n;i++)
	{
		cin>>s>>e>>d;
		a[s].push_back({e,d%2});
		a[e].push_back({s,d%2}); 
	}
	dfs(1,0,0);
	cout<<x*x*x+y*y*y;
}