记录编号	214211	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011] 聪聪可可	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.188 s
提交时间	2015-12-14 20:56:11	内存使用	1.14 MiB

#include<cstdio>
int n,u,v,w,shu,first[21000];
struct bian
{
	int v,w,nx;
}o[51000];
inline void add(int u,int v,int w)
{
	o[++shu].v=v;
	o[shu].w=w;
	o[shu].nx=first[u];
	first[u]=shu;
}
bool flag[21000];
int ans,root,now,S,num[3],s[21000],d[21000];
inline void dfs(int x,int last)
{
	s[x]=1;
	++num[d[x]%3];
	for(int i=first[x];i;i=o[i].nx)
		if(o[i].v!=last&&!flag[o[i].v])
		{
			d[o[i].v]=d[x]+o[i].w;
			dfs(o[i].v,x);
			s[x]+=s[o[i].v];
		}
	if(s[x]>S&&s[x]-S<now)
	{
		now=s[x]-S;
		root=x;
	}
}
inline void DFS(int x)
{
	flag[x]=1;
	d[x]=0;
	dfs(x,x);
	ans+=num[0]*num[0]+(num[1]*num[2]<<1);
	for(int i=first[x];i;i=o[i].nx)
		if(!flag[o[i].v])
		{
			S=s[o[i].v]>>1;
			now=0x7fffffff;
			num[0]=num[1]=num[2]=0;
			dfs(o[i].v,x);
			ans-=num[0]*num[0]+(num[1]*num[2]<<1);
			num[0]=num[1]=num[2]=0;
			DFS(root);
		}
}
int main()
{
	freopen("cckk.in","r",stdin);
	freopen("cckk.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;++i)
	{
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	now=0x7fffffff;
	S=n>>1;
	dfs(1,1);
	num[0]=num[1]=num[2]=0;
	DFS(root);
	int a=ans,b=n*n,c;
	while(b)
	{
		c=b;
		b=a%b;
		a=c;
	}
	printf("%d/%d",ans/a,n*n/a);
}