记录编号	293289	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011] 聪聪可可	最终得分	100
用户昵称	真呆菌	是否通过	通过
代码语言	C++	运行时间	0.180 s
提交时间	2016-08-10 13:24:24	内存使用	1.05 MiB

#include<cstdio>
using namespace std;
const int N = 20010;
int n,tot,root,aa,bb,gg;
int to[N<<1],nex[N<<1],val[N<<1],head[N];
int siz[N],h[N],us[N],pr[4],nr[4];

int Max(int x,int y){if(x>y) return x;return y;}

void SE(int u,int v,int w){
	to[++tot]=v;nex[tot]=head[u];head[u]=tot;val[tot]=w;
	return;
}

void Find_root(int x,int fa,int totv){
	siz[x]=1;h[x]=0;
	for(int i=head[x];i;i=nex[i]){
		if(us[to[i]]||to[i]==fa) continue;
		Find_root(to[i],x,totv);
		siz[x]+=siz[to[i]];
		h[x]=Max(h[x],siz[to[i]]);
	}
	h[x]=Max(h[x],totv-siz[x]);
	if(h[x]<h[root]) root=x;
	return;
}

void Calc(int x,int fa,int ad){
	nr[ad]++;
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa||us[to[i]]) continue;
		Calc(to[i],x,(ad+val[i])%3);
	}
	return;
}

int DC(int x){
	us[x]=1;
	int res=0;
	for(int i=0;i<=2;i++) pr[i]=nr[i]=0;
	pr[0]=1;
	for(int i=head[x];i;i=nex[i]){
		if(us[to[i]]) continue;
		for(int j=0;j<=2;j++) nr[j]=0;
		Calc(to[i],x,val[i]);
		for(int j=0;j<=2;j++) res+=nr[j]*pr[(3-j)%3];
		for(int j=0;j<=2;j++) pr[j]+=nr[j];
	}
	
	for(int i=head[x];i;i=nex[i]){
		if(us[to[i]]) continue;
		root=0;
		Find_root(to[i],x,siz[to[i]]);
		res+=DC(root);
	}
	
	return res;
}

int Gcd(int x,int y){
	int r=x%y;
	while(r){
		x=y;
		y=r;
		r=x%y;
	}
	return y;
}

int main(){
	freopen("cckk.in","r",stdin);
	freopen("cckk.out","w",stdout);
	scanf("%d",&n);
	for(int u,w,v,i=1;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);
		SE(u,v,w%3);SE(v,u,w%3);
	}
	h[0]=233333333;
	root=0;
	Find_root(1,1,n);
	aa=DC(root)*2+n;
	bb=n*n;
	//printf("%d %d\n",aa,bb);
	gg=Gcd(aa,bb);
	printf("%d/%d\n",aa/gg,bb/gg);
	return 0;
}