记录编号	494762	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011] 聪聪可可	最终得分	100
用户昵称	サイタマ	是否通过	通过
代码语言	C++	运行时间	0.416 s
提交时间	2018-04-13 17:27:16	内存使用	0.71 MiB

#include<cstdio>
#include<vector>
#define Max(a,b) a>b?a:b
using namespace std;
int n,root,sum,f[20010],t[3],ans,deep[20010],size[20010];
bool vis[20010];
class node
{public:
    int p,w;
}v;
vector<node> d[20010];
int gcd(int x,int y)
{
    return y?gcd(y,x%y):x;
}
void Get_root(int u,int fa)
{
    size[u]=1;
    f[u]=0;
    for(int i=0;i<d[u].size();i++)
    {
        int v=d[u][i].p;
        if(v==fa||vis[v])continue;
        Get_root(v,u);
        size[u]+=size[v];
        f[u]=Max(f[u],size[v]);
    }
    f[u]=Max(f[u],sum-size[u]);
    if(f[u]<f[root])root=u;
}
void Get_deep(int u,int fa)
{
    t[deep[u]]++;
    for(int i=0;i<d[u].size();i++)
    {
        int v=d[u][i].p;
        int w=d[u][i].w;
        if(fa==v||vis[v])continue;
        deep[v]=(deep[u]+w)%3;
        Get_deep(v,u);
    }
}
int Calc(int u,int w)
{
    deep[u]=w;
    t[0]=t[1]=t[2]=0;
    Get_deep(u,0);
    return t[0]*t[0]+t[1]*t[2]*2;
}
void Solve(int u)
{
    vis[u]=1;
    ans+=Calc(u,0);
    for(int i=0;i<d[u].size();i++)
    {
        int v=d[u][i].p;
        int w=d[u][i].w;
        if(vis[v])continue;
        ans-=Calc(v,w);
        sum=size[u];
        root=0;
        Get_root(v,0);
        Solve(root);
    }
}
int lyh()
{
    freopen("cckk.in","r",stdin);
    freopen("cckk.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d%d",&a,&b,&v.w);
        v.w%=3;
        v.p=a;
        d[b].push_back(v);
        v.p=b;
        d[a].push_back(v);
    }
    root=0;
    sum=n;
    f[0]=0x7fffffff;
    Get_root(1,0);
    Solve(root);
    n=n*n;
    int g=gcd(n,ans);
    printf("%d/%d\n",ans/g,n/g);
    return 0;
}
int Main=lyh();
int main(){;}