Miku

可以用树上dp解决

$dp_{i,j}$表示以i为根的子树在模三意义下到i的距离为j的点有几个

然后根据乘法原理搞一波

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int x,y,z;
const int maxn=200004;
int head[maxn+10];
int p;
int du[maxn];
int ans;
int dp[maxn][5];
struct e{
    int f;
    int to;
    int ne;
    int w;
} ed[maxn];
void add(int f,int t,int w){
    p++;
    ed[p].ne=head[f];
    ed[p].f=f;
    ed[p].w=w;
    ed[p].to=t;
    head[f]=p;
    return ;
}
void dfs(int now,int f){
    dp[now][0]=1;
    for(int i=head[now];i;i=ed[i].ne){
        if(ed[i].to!=f){
            dfs(ed[i].to,now);
        for(int j=0;j<=2;++j){
            ans+=dp[now][(3-(j+ed[i].w%3+3)%3)%3]*dp[ed[i].to][j]*2;
            //当前点也可以和now子树上之前的点门组合
            //只要距离合法 
        }   
        for(int j=0;j<=2;++j){
            dp[now][((j+ed[i].w)%3+3)%3]+=dp[ed[i].to][j];
        }
    }
    }
    return ;
}
int gcd(int x,int y){
    return y==0 ? x :gcd(y,x%y);
}
int anss;
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    anss=n*n;
    dfs(1,0);
    ans+=n;//选自己也可以哦 
    cout<<ans/gcd(ans,anss)<<"/"<<anss/gcd(ans,anss);
    return 0;
}