明显的点分治。

我们记\(num_{i,j}\)为点\(i\)及其子树中的节点与\(i\)之间的路径的和对3取余为\(j\)的种类数,显然\(0\le j<3\)。

我们再记\(val_{u,v}\)为两个直接相连的点\(u,v\)之间的边权,我们把边权和距离全部对3取余。

我们发现这个东西很好计算。基础的树形DP就好了。

那么如何统计答案呢?

当我们将一个节点\(v\)合并到它的父节点\(u\)上时,会产生2种新的路径:

1.以\(u\)为一端,\(v\)及其子树中的节点为另一端的;

2.以\(u\)已经合并的子树中的节点为一端,\(v​\)及其子树中的节点为另一端的。

考虑第一种,种类数就是\(2\times num_{v,3-val_{u,v}}\),乘2是因为可以调换链的两端。

对于第二种,我们记\(sum_i\)为已经合并的子树中,到\(u\)的距离为\(i\)的节点的数量。

那么这一种的种类数就是\(2\times \sum_{i=0}^2num_{v,i}\times sum_{3-i-val_{u,v}}\)。

最后输出的时候记得约分。

code:

#include
    
     #define V(x) (x>2?x-3:(x<0?x+3:x))using namespace std;struct edge{    int t,v,nxt;}e[40010];int n,u,v,w,be[20010],cnt,vis[20010];long long num[20010][3],ans;void add(const int &x,const int &y,const int &val){    e[++cnt].t=y,e[cnt].v=val,e[cnt].nxt=be[x],be[x]=cnt;}void Upd(const int &x,const int &y,const int &ev,long long *sum){    num[x][ev]+=num[y][0],num[x][V(ev+1)]+=num[y][1],num[x][V(ev+2)]+=num[y][2],ans+=num[y][V(3-ev)]*2;    for(int i=0;i<3;++i)ans+=num[y][i]*sum[V(V(3-ev)-i)]*2;    sum[ev]+=num[y][0],sum[V(ev+1)]+=num[y][1],sum[V(ev+2)]+=num[y][2];}void dfs(const int &x){    vis[x]=1,num[x][0]=1,ans++;    long long sum[3];    sum[0]=sum[1]=sum[2]=0;    for(int i=be[x];i;i=e[i].nxt)!vis[e[i].t]?dfs(e[i].t),Upd(x,e[i].t,e[i].v,sum),0:0;}long long gcd(const long long &x,const long long &y){    return y?gcd(y,x%y):x;}void Print(const long long &x,const long long &y){    long long g=gcd(x,y);    printf("%lld/%lld",x/g,y/g);}int main(){    scanf("%d",&n);    for(int i=1;i