记录编号	151748	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011] 聪聪可可	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.401 s
提交时间	2015-03-10 15:29:55	内存使用	7.37 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

#define Maxn 200010

using namespace std;

int n,m,root,leaf,siz[Maxn],dep[Maxn],maxv[Maxn],tot[3];
vector<int> G[Maxn],C[Maxn];
bool vis[Maxn];

int gcd(int a,int b){
	return b? gcd(b,a%b):a;
}

void find_root(int x,int tp){
	maxv[x]=0; siz[x]=1;
	for(int i=0;i<G[x].size();i++){
		if(G[x][i]==tp||vis[G[x][i]]) continue;
		find_root(G[x][i],x);
		siz[x]+=siz[G[x][i]];
		maxv[x]=max(maxv[x],siz[G[x][i]]);
	}
	maxv[x]=max(maxv[x],leaf-siz[x]);
	if(!root||maxv[x]<maxv[root])
		root=x;
}

void find_color(int x,int tp){
	tot[dep[x]]++;
	for(int i=0;i<G[x].size();i++){
		if(G[x][i]==tp||vis[G[x][i]]) continue;
		dep[G[x][i]]=dep[x]+C[x][i];
		if(dep[G[x][i]]>=3) dep[G[x][i]]-=3;
		find_color(G[x][i],x);
	}
}

int calc(int x,int v){
	tot[0]=tot[1]=tot[2]=0;
	dep[x]=v;
	find_color(x,x);
	return tot[0]*tot[0]+2*tot[2]*tot[1];
}

int DC(int x){
	int now=calc(x,0);
	//cout<<x<<endl;
	vis[x]=1;
	for(int i=0;i<G[x].size();i++){
		if(vis[G[x][i]]) continue;
		now-=calc(G[x][i],C[x][i]);
		root=0;
		leaf=siz[G[x][i]];
		find_root(G[x][i],G[x][i]);
		now+=DC(root);
	}
	return now;
}

void solve(){
	root=0; leaf=n;
	find_root(1,1);
	int num_up=DC(root),num_down=n*n;
	//cout<<"over DC\n";
	int d=gcd(num_up,num_down);
	printf("%d/%d\n",num_up/d,num_down/d);
}

void init(){
	memset(vis,0,sizeof(vis));
	scanf("%d",&n);
	int x,y,v;
	maxv[0]=0x3f3f3f3f;
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&v);
		v%=3;
		G[x].push_back(y);
		C[x].push_back(v);
		G[y].push_back(x);
		C[y].push_back(v);
	}
}

int main(){
	freopen("cckk.in","r",stdin);
	freopen("cckk.out","w",stdout);
	init();
	//cout<<"over init\n";
	solve();
	return 0;
}