记录编号	481553	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011] 聪聪可可	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.237 s
提交时间	2018-01-03 14:31:57	内存使用	3.71 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define N 80100
char xB[(1<<15)+10],*xS=xB,*xT=xB;
#define gtc (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline void read(int &shu){
	register char ch=gtc;
	for(shu=0;ch<'0'||ch>'9';ch=gtc);
	for(;ch>='0'&&ch<='9';shu=(shu<<1)+(shu<<3)+ch-'0',ch=gtc);
}
int n,k;
struct haha{
	int next,to,w;
}edge[N*2];
int head[N],cnt=1;
inline void add(int u,int v,int w){
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
int size[N],vis[N];
int root,cntsize=0x7fffffff,tot;
inline void getroot(int x,int fa){
	size[x]=1;
	int res(0);
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(!vis[to]&&to!=fa){
			getroot(to,x);
			size[x]+=size[to];
			res=max(res,size[to]);
		}
	}
	res=max(res,tot-size[x]);
	if(res<cntsize){
		cntsize=res;root=x;
	}
}
int ans[N],haha,fenmu;
int stack[N],hea;
inline void dfs(int x,int fa,int ww){
	size[x]=1;stack[++hea]=ww;
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to,w=edge[i].w;
		if(to!=fa&&!vis[to]){
			dfs(to,x,(ww+w)%3);
			size[x]+=size[to];
		}
	}
}
int jishu[3];
inline int cal(int x,int dis){
	hea=0;dfs(x,0,dis);
	int res(0);jishu[0]=jishu[1]=jishu[2]=0;
	pos(i,1,hea){
		jishu[stack[i]]++;
	}
	res+=jishu[0]*(jishu[0]-1);
	res+=jishu[1]*jishu[2]*2;
	return res;
}
inline void work(int x){
	vis[x]=1;
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(!vis[to]) ans[x]-=cal(to,edge[i].w);
	}
	ans[x]+=cal(x,0);
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(!vis[to]){
			tot=size[to];cntsize=0x7fffffff;
			getroot(to,x);
			work(root);
		}
	}
	haha+=ans[x];
}
int gcd(int a,int b){if(!b) return a;return gcd(b,a%b);}
int main(){
	freopen("cckk.in","r",stdin);
	freopen("cckk.out","w",stdout);
	read(n);fenmu=n*n;
	pos(i,1,n-1){
		int x,y,z;read(x);read(y);read(z);z%=3;
		add(x,y,z);add(y,x,z);
	}
	tot=n;getroot(1,0);
	work(root);
	haha+=n;
	int g=gcd(haha,fenmu);haha/=g;fenmu/=g;
	printf("%d/%d",haha,fenmu);
	return 0;
}