求助大佬,蜜汁TLE

回复帖子

@zhy12138 2018-08-10 23:23 回复

如题

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
#define ll long long
using namespace std;
int read()
{
    int kkk=0;
    char c=getchar();
    while(c<'0' || c>'9')
        c=getchar();
    while(c>='0' && c<='9')
        kkk=(kkk<<3)+(kkk<<1)+(c-'0'),c=getchar();
    return kkk;
}
int n,tot,maxn,ans,root,z,head[20010],size[20010],maxsize[20010],dis[3];
char pd[20010];
int mood(int k)
{
    if(k>=3)
        return k-3;
    return k;
}
struct sb
{
    int to,nextn,l;
}a[40010];
int ADD(int from,int to,int l)
{
    ++tot;
    a[tot].to=to,a[tot].l=l%3,a[tot].nextn=head[from],head[from]=tot;
}
int find(int u,int fa)
{
    size[u]=1,maxsize[u]=0;
    for(int i=head[u];i!=0;i=a[i].nextn)
    {
        int v=a[i].to;
        if(pd[v]==1 || v==fa)
            continue;
        find(v,u);
        size[u]=+size[v],maxsize[u]=(maxsize[u]>size[v]?maxsize[u]:size[v]);
    }
    maxsize[u]=(maxsize[u]>z-size[u]?maxsize[u]:z-size[u]);
    if(maxsize[u]<maxn)
        root=u,maxn=maxsize[u];
}
int run(int u,int fa,int l)
{
    ++dis[l];
    for(int i=head[u];i!=0;i=a[i].nextn)
    {
        int v=a[i].to;
        if(pd[v]==1 || v==fa)
            continue;
        run(v,u,mood(l+a[i].l));
    }
}
int fun(int Root)
{
    pd[Root]=1,dis[0]=dis[1]=dis[2]=0;
    run(Root,0,0);
    ans+=dis[0]*dis[0]+2*dis[1]*dis[2];
    for(int i=head[Root];i!=0;i=a[i].nextn)
    {
        int v=a[i].to;
        if(pd[v]==1)
            continue;
        dis[0]=dis[1]=dis[2]=0;
        run(v,Root,a[i].l);
        ans-=dis[0]*dis[0]+2*dis[1]*dis[2];
        maxn=0x7f7f7f7f,root=0,z=size[v];
        find(v,Root),fun(root);
    }
}
int gcd(int x,int y)
{
    int z=x%y;
    while(z!=0)
        x=y,y=z,z=x%y;
    return y;
}
int main()
{
    n=read();
    for(int i=1;i<n;++i)
    {
        int u=read(),v=read(),k=read();
        ADD(u,v,k),ADD(v,u,k);
    }
    maxn=0x7f7f7f7f,root=0,z=n;
    find(1,0),fun(root);
    int g=gcd(ans,n*n);
    printf("%d/%d",ans/g,n*n/g);
    return 0;
}
@zhy12138 2018-08-10 23:51 回复

不用了,BUG已找到

size[u]=+size[v],maxsize[u]=(maxsize[u]>size[v]?maxsize[u]:size[v]);

=+ 和 += ???

我*

希望给后面的同学一个提醒,这种码量适中的题是真的恶心优秀

@zhy12138 2018-08-10 23:52 回复

询问大神,+=和=+会出一样的结果吗?

@zhy12138 2018-08-10 23:54 回复

那我还A了7个点,数据是真的水