题意：
一棵有边权的树，问有多少对点的简单路径权值和模3为0
思路：
简单的树分治，每次处理出重心后，处理出到重心的距离，然后为0的直接平方，1和2的相乘并乘2（因为（2，3），（3，2）算两对），然后删去不合法的对数，再删去重心。
重复以上过程就行了
错误及反思：
发现难的树分治不会，还是刷刷简单的慢慢来吧
还有，他们是怎么跑到100多的。。。
代码：
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 20010;
struct EDGE{int to,next,val;
}e[N*2];
int first[N],n,tot=0,si[N],maxn[N],num[3];
bool did[N];
inline int read()
{int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;
}
void addedge(int x,int y,int z){e[tot].to=y;e[tot].val=z;e[tot].next=first[x];first[x]=tot++;e[tot].to=x;e[tot].val=z;e[tot].next=first[y];first[y]=tot++;
}
void dfs1(int now,int fa){si[now]=1;maxn[now]=0;for(int i=first[now];i!=-1;i=e[i].next)if(e[i].to!=fa&&!did[e[i].to]){dfs1(e[i].to,now);si[now]+=si[e[i].to];maxn[now]=max(maxn[now],si[e[i].to]);}
}
void dfs3(int now,int fa,int& root,int& num,int t){int MA=max(maxn[now],si[t]-si[now]);if(MA<num){num=MA;root=now;}for(int i=first[now];i!=-1;i=e[i].next)if(e[i].to!=fa&&!did[e[i].to])dfs3(e[i].to,now,root,num,t);
}
void dfs2(int now,int fa,int tlen){tlen%=3;for(int i=first[now];i!=-1;i=e[i].next)if(e[i].to!=fa&&!did[e[i].to])dfs2(e[i].to,now,tlen+e[i].val);num[tlen]++;
}
int cal(int now,int d){memset(num,0,sizeof(num));dfs2(now,-1,d);int ans=num[0]*num[0];ans+=num[1]*num[2]*2;return ans;
}
int solve(int now){int root,num=1e9;dfs1(now,-1);dfs3(now,-1,root,num,now);int ans=cal(root,0);did[root]=true;for(int i=first[root];i!=-1;i=e[i].next)if(!did[e[i].to]){ans-=cal(e[i].to,e[i].val);ans+=solve(e[i].to);}return ans;
}
int main(){memset(first,-1,sizeof(first));n=read();for(int i=0,u,v,w;i<n-1;i++){u=read(),v=read(),w=read();addedge(u,v,w);}int a=solve(1);int b=n*n;int c=__gcd(a,b);a/=c;b/=c;printf("%d/%d\n",a,b);
}