洛谷 P2634 [国家集训队]聪聪可可

点分板子2333

注释都是错过的地方

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 struct E

 {

     LL to,nxt,d;

 }e[];

 LL f1[],ne,sz[];

 LL n,sum,root,dep[],ans,fx[];

 LL tmp[];

 bool vis[];

 void getroot(LL u,LL fa)

 {

     sz[u]=;fx[u]=;

     for(LL k=f1[u];k;k=e[k].nxt)

         if(!vis[e[k].to]&&e[k].to!=fa)

         {

             getroot(e[k].to,u);

             sz[u]+=sz[e[k].to];

             fx[u]=max(fx[u],sz[e[k].to]);

         }

     fx[u]=max(fx[u],sum-sz[u]);

     if(fx[u]<fx[root])    root=u;

 }

 void getsz(LL u,LL fa)

 {

     sz[u]=;

     for(LL k=f1[u];k;k=e[k].nxt)

         if(!vis[e[k].to]&&e[k].to!=fa)

         {

             getsz(e[k].to,u);

             sz[u]+=sz[e[k].to];

         }

 }

 void getdeep(LL u,LL fa)

 {

     tmp[dep[u]%]++;

     for(LL k=f1[u];k;k=e[k].nxt)

         if(!vis[e[k].to]&&e[k].to!=fa)

         {

             dep[e[k].to]=dep[u]+e[k].d;

             getdeep(e[k].to,u);

         }

 }

 LL cal(LL u,LL cost)

 {

     tmp[]=tmp[]=tmp[]=;dep[u]=cost;

     getdeep(u,);

     return tmp[]*tmp[]+*tmp[]*tmp[];

 }

 void solve(LL u)

 {

     ans+=cal(u,);

     vis[u]=;//

     for(LL k=f1[u];k;k=e[k].nxt)

         if(!vis[e[k].to])

         {

             //vis[e[k].to]=1;

             getsz(e[k].to,);

             sum=sz[e[k].to];//

             root=;getroot(e[k].to,);

             ans-=cal(e[k].to,e[k].d);//ans-=cal(e[k].to,u);

             solve(root);

         }

 }

 int main()

 {

     LL i,x,y,w;

     fx[]=0x3f3f3f3f;

     scanf("%lld",&n);

     for(i=;i<n;i++)

     {

         scanf("%lld%lld%lld",&x,&y,&w);

         e[++ne].to=y;e[ne].nxt=f1[x];e[ne].d=w;f1[x]=ne;

         e[++ne].to=x;e[ne].nxt=f1[y];e[ne].d=w;f1[y]=ne;

     }

     sum=n;getroot(,);

     solve(root);

     LL a1=ans,a2=n*n;LL g=__gcd(a1,a2);

     a1/=g;a2/=g;

     printf("%lld/%lld",a1,a2);

     return ;

 }