点分治裸题，不说了。
对于这道题目，我们找的就是长度和为3的倍数的路径条数，根据模运算性质，我们可以将所有路径长模3。
那么，就可以用点分治的基本操作解决此题了。
代码稍微参考了一下这位dalao的：GO
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=4e4+10; 4 int n,cnt,rt,ans,size; 5 int head[N<<1],ms[N],jud[N],sum[N],dep[N],siz[N]; 6 struct edge{int to,next,w;}e[N<<1]; 7 void addedge(int from,int to,int w){e[++cnt]=(edge){to,head[from],w};head[from]=cnt;} 8 int read(){ 9 int x=0,f=1; 10 char c=getchar(); 11 while(!isdigit(c)){ 12 if(c=='-') f=-1; 13 c=getchar(); 14 } 15 while(isdigit(c)){ 16 x=x*10+c-'0'; 17 c=getchar(); 18 } 19 return x*f; 20 } 21 void grt(int u,int f){ 22 siz[u]=1;ms[u]=0; 23 for(int i=head[u];i;i=e[i].next){ 24 int v=e[i].to; 25 if(v==f||jud[v]) continue; 26 grt(v,u); 27 siz[u]+=siz[v]; 28 ms[u]=max(ms[u],siz[v]); 29 } 30 ms[u]=max(ms[u],size-siz[u]); 31 if(ms[u]<ms[rt]) rt=u; 32 } 33 void gdp(int u,int fa){ 34 sum[dep[u]]++; 35 for(int i=head[u];i;i=e[i].next){ 36 int v=e[i].to,w=e[i].w; 37 if(v==fa||jud[v]) continue; 38 dep[v]=(dep[u]+w)%3; 39 gdp(v,u); 40 } 41 } 42 int calc(int u,int p){ 43 sum[0]=sum[1]=sum[2]=0; 44 dep[u]=p; 45 gdp(u,0); 46 return sum[0]*sum[0]+sum[1]*sum[2]*2; 47 } 48 void solve(int u){ 49 ans+=calc(u,0); 50 jud[u]=1; 51 for(int i=head[u];i;i=e[i].next){ 52 int v=e[i].to,w=e[i].w; 53 if(jud[v]) continue; 54 ans-=calc(v,w); 55 rt=0; 56 size=ms[v]; 57 grt(v,0); 58 solve(rt); 59 } 60 } 61 int gcd(int x,int y){ 62 return y==0?x:gcd(y,x%y); 63 } 64 int main(){ 65 n=read(); 66 int x,y,z; 67 for(int i=1;i<n;i++){ 68 x=read();y=read();z=read(); 69 z%=3; 70 addedge(x,y,z); 71 addedge(y,x,z); 72 } 73 size=ms[rt]=n; 74 grt(1,0); 75 solve(rt); 76 x=gcd(ans,n*n); 77 printf("%d/%d",ans/x,n*n/x); 78 return 0; 79 }