树分治，每次统计时有两种组合%3==2和%3==1, %3==0和%3==0
乘法原理即可
# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
IL ll Read(){
RG char c = getchar(); RG ll x = 0, z = 1;
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
return x * z;
}
const int MAXN(40010), INF(2147483647);
int n, cnt, fst[MAXN], to[MAXN], nxt[MAXN], w[MAXN];
int size[MAXN], rt, sz, mx[MAXN], vis[MAXN];
ll d[3], num;
IL void Add(RG int u, RG int v, RG int f){ nxt[cnt] = fst[u]; to[cnt] = v; w[cnt] = f; fst[u] = cnt++; }
IL void Getroot(RG int u, RG int fa){
size[u] = 1; mx[u] = 0;
for(RG int e = fst[u]; e != -1; e = nxt[e]){
if(vis[to[e]] || fa == to[e]) continue;
Getroot(to[e], u);
size[u] += size[to[e]];
mx[u] = max(mx[u], size[to[e]]);
}
mx[u] = max(mx[u], sz - size[u]);
if(mx[u] < mx[rt]) rt = u;
}
IL void Getdeep(RG int u, RG int fa, RG int dis){
d[dis % 3]++;
for(RG int e = fst[u]; e != -1; e = nxt[e]){
if(vis[to[e]] || fa == to[e]) continue;
Getdeep(to[e], u, (dis + w[e]) % 3);
}
}
IL ll Calc(RG int u, RG int ww){
d[0] = d[1] = d[2] = 0;
Getdeep(u, 0, ww);
return d[1] * d[2] * 2 + d[0] * d[0];
}
IL void Solve(RG int u){
vis[u] = 1; num += Calc(u, 0);
for(RG int e = fst[u]; e != -1; e = nxt[e]){
if(vis[to[e]]) continue;
num -= Calc(to[e], w[e]);
rt = 0; sz = size[to[e]];
Getroot(to[e], u);
Solve(rt);
}
}
IL ll Gcd(RG ll a, RG ll b){ return !a ? b : Gcd(b % a, a); }
int main(RG int argc, RG char* argv[]){
n = Read(); Fill(fst, -1);
for(RG int i = 1; i < n; i++){
RG int u = Read(), v = Read(), f = Read();
Add(u, v, f); Add(v, u, f);
}
mx[0] = INF; sz = n; Getroot(1, 0); Solve(rt);
RG ll a = num, b = 1LL * n * n, g = Gcd(a, b);
printf("%lld/%lld
", a / g, b / g);
return 0;
}