也许本身想去写点分治的，但是最后因为码量太大就放弃了
然后就顺手写了个树形$dp$，其实跟点分治的思想一样，我们只要每次统计一条路径的上端点，什么意思呢，就是我们将要统计$(u,v)$是否合法呢，只要去$lca(u,v)$就行。然后就定$dp$数组为$dp(i,j)$表示为当前到第i个节点，并且现在长度对$3$取模为的方案数，然后就可以随便$dp$了
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int MAXN=20001; int gcd(int x,int y){ if(y==0) return x; return gcd(y,x%y); } struct node{ int u,v,w,nex; }x[MAXN<<1]; int dp[MAXN][4],n,head[MAXN],cnt;//dp(i,j)表示在第i颗子树上选择距离为j%3的方案数 void add(int u,int v,int w){ x[cnt].u=u,x[cnt].v=v,x[cnt].w=w,x[cnt].nex=head[u],head[u]=cnt++; } int ans; void dfs(int f,int fath){ dp[f][0]=1; for(int ii=head[f];ii!=-1;ii=x[ii].nex){ if(x[ii].v==fath) continue; dfs(x[ii].v,f); for(int i=0;i<3;i++){ int w=x[ii].w%3; ans+=dp[x[ii].v][i]*dp[f][(3-((i+w)%3))%3]*2; } for(int i=0;i<3;i++) dp[f][(i+x[ii].w)%3]+=dp[x[ii].v][i]; } return; } int main(){ memset(head,-1,sizeof(head)); n=read(); for(int i=1;i<n;i++){ int u=read(),v=read(),w=read(); add(u,v,w),add(v,u,w); } dfs(1,0); ans+=n; int fz=ans,fm=n*n; int k=gcd(fz,fm); fz/=k,fm/=k; printf("%d/%d",fz,fm); }