rt

吸了氧以后9，10点1.08s

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int  n;
int root;
struct Node{
	int to,val;
	Node(int to,int val) :to(to),val(val){}
};
int weigh[40005],size[40005],d[40005],a[40005];
bool vis[40005];
int rootsize;
int  ans;
int g,h,ph;
vector <Node > e[40005];
void add(int u,int v,int ww){
	e[u].push_back(Node(v,ww%3));
	e[v].push_back(Node(u,ww%3));
}
inline void getcentral(int now,int fa){
	size[now]=1,weigh[now]=0;
	for(register int i=0;i<e[now].size();++i){
		int to=e[now][i].to;
		if(to==fa||vis[to]) continue;
		getcentral(to,now);
		size[now]+=size[to];
		weigh[now]=max(weigh[now],size[to]);
	}
	weigh[now]=max(weigh[now],rootsize-size[now]);
	if(weigh[root]>weigh[now]) root=now;
}
inline void dfs(int now,int fa){
	a[d[now]]++;
	for(register int i=0;i<e[now].size();++i){
		register int to=e[now][i].to;
		if(vis[to]||fa==to) continue;
		d[to]=(d[now]+e[now][i].val)%3;
		dfs(to,now);
	}
}
inline int calculate(int now){
	a[0]=a[1]=a[2]=0;
	dfs(now,0);
	return a[0]*a[0]+2*a[1]*a[2];
}
inline void divide(int now){
	vis[now]=1;
	d[now]=0;
	ans+=calculate(now);
	for(register int i=0;i<e[now].size();++i){
		register int to=e[now][i].to;
		if(vis[to]) continue;
		d[to]=e[now][i].val;
		ans-=calculate(to);
		root=to;
		rootsize=size[to];
		weigh[to]=0x3f3f3f;
		getcentral(to,0);
		divide(root);
	}
}
inline int gcd(int x,int y){
	if(!y) return x;
	return gcd(y,x%y);
}
inline int read(){
	register int w=0,x=0;char ch;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return w?-x:x;
}
signed main(){
	n=read();
	for(register int i=1;i<=n-1;++i){
		g=read(),h=read(),ph=read();
		add(g,h,ph);
	}
    rootsize=n,weigh[root]=0x3f3f3f;
	getcentral(1,0);
	divide(root);
	int ggg=gcd(ans,n*n);
	printf("%d/%d",ans/ggg,n*n/ggg);
	return 0;
}