我们知道一共有n^2种取法，那么我们无需计算概率，只需统计有多少取法能满足mod 3=0就行了。
那这道题就是经典的点分治套路了。
把路径长mod 3之后，统计长为0，1，2的分别有多少。
然后0和0可以合到一起，1和2可以合到一起。
注意(1,2)和(2,1)算两种。
最后分子分母同除gcd就行了。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int n,ans; 7 int hd[20005],to[40005],nx[40005],len[40005],ec; 8 9 void edge(int af,int at,int el) 10 { 11 to[++ec]=at; 12 len[ec]=el; 13 nx[ec]=hd[af]; 14 hd[af]=ec; 15 } 16 17 int rt,tot; 18 int del[20005]; 19 int sz[20005],mx[20005]; 20 int dis[20005],cnt[3]; 21 22 void weigh(int p,int fa) 23 { 24 sz[p]=1;mx[p]=0; 25 for(int i=hd[p];i;i=nx[i]) 26 { 27 int tar=to[i]; 28 if(tar==fa||del[tar])continue; 29 weigh(tar,p); 30 sz[p]+=sz[tar]; 31 mx[p]=max(mx[p],sz[tar]); 32 } 33 mx[p]=max(mx[p],tot-sz[p]); 34 if(mx[p]<mx[rt])rt=p; 35 } 36 37 void dfs(int p,int fa) 38 { 39 cnt[dis[p]%3]++; 40 for(int i=hd[p];i;i=nx[i]) 41 { 42 int tar=to[i]; 43 if(tar==fa||del[tar])continue; 44 dis[tar]=dis[p]+len[i]; 45 dfs(tar,p); 46 } 47 } 48 49 int count(int p,int d0) 50 { 51 dis[p]=d0; 52 cnt[0]=cnt[1]=cnt[2]=0; 53 dfs(p,0); 54 return cnt[0]*cnt[0]+cnt[1]*cnt[2]*2; 55 } 56 57 void conquer(int p) 58 { 59 del[p]=1; 60 ans+=count(p,0); 61 for(int i=hd[p];i;i=nx[i]) 62 { 63 int tar=to[i]; 64 if(del[tar])continue; 65 ans-=count(tar,len[i]); 66 rt=0;tot=sz[tar]; 67 weigh(tar,0); 68 conquer(rt); 69 } 70 } 71 72 int gcd(int x,int y) 73 { 74 return y?gcd(y,x%y):x; 75 } 76 77 int main() 78 { 79 scanf("%d",&n); 80 for(int i=1;i<n;i++) 81 { 82 int ff,tt,vv; 83 scanf("%d%d%d",&ff,&tt,&vv); 84 edge(ff,tt,vv%3); 85 edge(tt,ff,vv%3); 86 } 87 mx[0]=tot=n; 88 weigh(1,0); 89 conquer(rt); 90 tot=n*n; 91 int g=gcd(ans,tot); 92 ans/=g;tot/=g; 93 printf("%d/%d",ans,tot); 94 return 0; 95 }