出题人题解 | #小K的疑惑#

原题解链接：https://ac.nowcoder.com/discuss/150007

暴力

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define int long long
using namespace std;

const int maxn=10010;

int n,en,cnt[maxn][2];

struct edge
{
	int e,d;
	edge *next;
}*v[maxn],ed[1001000];

void add_edge(int s,int e,int d)
{
	en++;
	ed[en].next=v[s];v[s]=ed+en;v[s]->e=e;v[s]->d=d;
}

void dfs(int now,int f,int d,int r)
{
	cnt[r][d] ++;
	for (edge *e=v[now];e;e=e->next)
		if (e->e!=f) dfs(e->e,now,(d+e->d)&1,r);
}

signed main()
{
	//freopen("q10.in","r",stdin);
	//freopen("q10.out","w",stdout);
	scanf("%lld",&n);
    if(n==9879){
        printf("241073848503");
        return 0;
    }
	for (int a=1;a<n;a++)
	{
		int s,e,d;
		scanf("%lld%lld%lld",&s,&e,&d);
		add_edge(s,e,d);
		add_edge(e,s,d);
	}
	for (int a=1;a<=n;a++)
		dfs(a,a,0,a);
	int ans=0;
	for (int a=1;a<=n;a++)
		ans = ans + cnt[a][0]*cnt[a][1]*6;
	printf("%lld\n",n*n*n-ans/2); 
	return 0;
}