聪聪可可

对于每个点，统计过他的边的对三取模的个数。看代码。

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=20005;
int beg[maxn],nex[maxn*2],to[maxn*2],w[maxn*2],e;
inline void add(int x,int y,int z){
    e++;nex[e]=beg[x];
    beg[x]=e;to[e]=y;w[e]=z;
}
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,mx,rt,size,ans;
int sz[maxn],son[maxn];
int vis[maxn],tmp[5],dp[maxn][5];
inline void getrt(int x,int fa){
    sz[x]=1;son[x]=0;
    for(int i=beg[x];i;i=nex[i]){
        int t=to[i];
        if(t==fa||vis[t])continue;
        getrt(t,x);
        sz[x]+=sz[t];
        if(sz[t]>son[x])son[x]=sz[t];
    }
    if(son[x]<size-sz[x])son[x]=size-sz[x];
    if(son[x]<mx)mx=son[x],rt=x;
}

inline void calc(int x,int fa,int val){
    tmp[val%3]++;
    for(int i=beg[x];i;i=nex[i]){
        int t=to[i];
        if(t==fa||vis[t])continue;
        calc(t,x,w[i]+val);
    }
}
inline void divide(int x){
    vis[x]=1;
    int tp[5];
    tp[0]=tp[1]=tp[2]=0;
    for(int i=beg[x];i;i=nex[i]){
        int t=to[i];
        if(vis[t])continue;
        tmp[0]=tmp[1]=tmp[2]=0;
        calc(t,x,w[i]);
        dp[x][0]=dp[x][0]+2*tmp[0]+2*tmp[0]*tp[0]+2*tmp[1]*tp[2]+2*tmp[2]*tp[1];
        dp[x][1]=dp[x][1]+2*tmp[1]+2*tmp[0]*tp[1]+2*tmp[1]*tp[0]+2*tmp[2]*tp[2];
        dp[x][2]=dp[x][2]+2*tmp[2]+2*tmp[0]*tp[2]+2*tmp[1]*tp[1]+2*tmp[2]*tp[0];
        tp[0]+=tmp[0],tp[1]+=tmp[1],tp[2]+=tmp[2];
        mx=inf,rt=0,size=sz[t];
        getrt(t,x);
        divide(rt);
    }
    dp[x][0]++;
    ans+=dp[x][0];
    //printf("%d %d
",x,dp[x][0]);
}
inline int gcd(int x,int y){
    if(y==0)return x;
    return gcd(y,x%y);
}
int main(){
    cin>>n;
    int x,y,z;
    for(int i=1;i<n;i++){
        x=read(),y=read(),z=read();
        add(x,y,z);add(y,x,z);
    }
    mx=inf,rt=0,size=n;
    getrt(1,0);
    divide(rt);
    int t=gcd(ans,n*n);
    printf("%d/%d
",ans/t,n*n/t);
    return 0;
}

很板子的一道题哈！