点分板子2333
注释都是错过的地方
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 typedef long long LL; 5 struct E 6 { 7 LL to,nxt,d; 8 }e[40100]; 9 LL f1[20010],ne,sz[20010]; 10 LL n,sum,root,dep[20010],ans,fx[20010]; 11 LL tmp[3]; 12 bool vis[20010]; 13 void getroot(LL u,LL fa) 14 { 15 sz[u]=1;fx[u]=0; 16 for(LL k=f1[u];k;k=e[k].nxt) 17 if(!vis[e[k].to]&&e[k].to!=fa) 18 { 19 getroot(e[k].to,u); 20 sz[u]+=sz[e[k].to]; 21 fx[u]=max(fx[u],sz[e[k].to]); 22 } 23 fx[u]=max(fx[u],sum-sz[u]); 24 if(fx[u]<fx[root]) root=u; 25 } 26 void getsz(LL u,LL fa) 27 { 28 sz[u]=1; 29 for(LL k=f1[u];k;k=e[k].nxt) 30 if(!vis[e[k].to]&&e[k].to!=fa) 31 { 32 getsz(e[k].to,u); 33 sz[u]+=sz[e[k].to]; 34 } 35 } 36 void getdeep(LL u,LL fa) 37 { 38 tmp[dep[u]%3]++; 39 for(LL k=f1[u];k;k=e[k].nxt) 40 if(!vis[e[k].to]&&e[k].to!=fa) 41 { 42 dep[e[k].to]=dep[u]+e[k].d; 43 getdeep(e[k].to,u); 44 } 45 } 46 LL cal(LL u,LL cost) 47 { 48 tmp[0]=tmp[1]=tmp[2]=0;dep[u]=cost; 49 getdeep(u,0); 50 return tmp[0]*tmp[0]+2*tmp[1]*tmp[2]; 51 } 52 void solve(LL u) 53 { 54 ans+=cal(u,0); 55 vis[u]=1;// 56 for(LL k=f1[u];k;k=e[k].nxt) 57 if(!vis[e[k].to]) 58 { 59 //vis[e[k].to]=1; 60 getsz(e[k].to,0); 61 sum=sz[e[k].to];// 62 root=0;getroot(e[k].to,0); 63 ans-=cal(e[k].to,e[k].d);//ans-=cal(e[k].to,u); 64 solve(root); 65 } 66 } 67 int main() 68 { 69 LL i,x,y,w; 70 fx[0]=0x3f3f3f3f; 71 scanf("%lld",&n); 72 for(i=1;i<n;i++) 73 { 74 scanf("%lld%lld%lld",&x,&y,&w); 75 e[++ne].to=y;e[ne].nxt=f1[x];e[ne].d=w;f1[x]=ne; 76 e[++ne].to=x;e[ne].nxt=f1[y];e[ne].d=w;f1[y]=ne; 77 } 78 sum=n;getroot(1,0); 79 solve(root); 80 LL a1=ans,a2=n*n;LL g=__gcd(a1,a2); 81 a1/=g;a2/=g; 82 printf("%lld/%lld",a1,a2); 83 return 0; 84 }