题目
转化题意：求权值是 3 的倍数的路径数量。
分析
我们直接把所有路径转化成模 3 意义下的数，然后其实就是询问权值和为 (0/3) 的路径个数。
直接套板子即可。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)) f|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;return;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);return;
}
#define ll long long
const int N=5e5+5,M=1e7+5,INF=1e9+7;
int n,m;
int head[N],nex[N],to[N],val[N],idx;
bool vis[N],Vis[N];
int app[M],Ans;
int siz[N],path[N],clear[N];
int Root,NowMax,path_cnt,Cnt,Size;
inline void add(int u,int v,int w){
nex[++idx]=head[u];
to[idx]=v;
val[idx]=w;
head[u]=idx;
return ;
}
void FindRoot(int x){
vis[x]=true;siz[x]=1;int Max=0;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(vis[y]||Vis[y]) continue;
FindRoot(y);siz[x]+=siz[y];
Max=max(siz[y],Max);
}
Max=max(Size-siz[x],Max);
if(Max<NowMax) NowMax=Max,Root=x;
vis[x]=false;
return ;
}
void GetPath(int x,int D){
path[++path_cnt]=D%m;vis[x]=true;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(vis[y]||Vis[y]) continue;
GetPath(y,D+val[i]);
}
vis[x]=false;
return ;
}
void DFS(int x){
Vis[x]=true;Cnt=0;app[0]=1;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(Vis[y]) continue;
path_cnt=0;GetPath(y,val[i]);
for(int k=1;k<=path_cnt;k++) Ans+=app[(m-path[k])%m];
for(int j=1;j<=path_cnt;j++) app[path[j]]++,clear[++Cnt]=path[j];
}
for(int i=1;i<=Cnt;i++) app[clear[i]]=0;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(Vis[y]) continue;
Size=siz[y],NowMax=n,Root=0,FindRoot(y);DFS(Root);
}
return ;
}
signed main(){
read(n);m=3;
for(int i=1;i<n;i++){
int u,v,w;
read(u),read(v),read(w);
add(u,v,w),add(v,u,w);
}
Ans=0;
Size=n,NowMax=n,Root=0,FindRoot(1),DFS(Root);
Ans=Ans*2+n;
int gcd=__gcd(Ans,n*n);
write(Ans/gcd),putchar('/'),write(n*n/gcd);
return 0;
}