题目大意

给出一棵有$n$个节点的无根树

若两个点路径上边的边权和是$3$的倍数，求这样的点对个数

数据范围

$n \leqslant 20000$

题解

学习树分治这段时间，安利一个博客 -> 戳我

对于每次分治的子树，两个点路径有两种情况

1. 经过根节点

可以把当前分治的这棵树上每一个节点到根节点的路径上边的边权和都记录下来

用$t[i]$表示有多少个节点到根节点的路径上边的边权和，在模$3$意义下为i

然后每次加上$(t[1] \times t[2]+t[2] \times t[1]+t[0] \times t[0])$

1. 不经过根节点

由于这些点对在情况$1$中被计算过一次

即同在一棵子树中的结点$A,B$，计算中路径多了$LCA(A,B)$到根节点的一段多余的路径

所以需要去掉这些贡献

然后路径不经过根节点的这些点对就可以分治到更小的子树去验证

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'&&ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,et,ans,root,sum;
struct edge{int to,next,c;}e[50050];
int last[20050],size[20050],f[20050],d[20050],t[5];
int vis[20050];

inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
inline void addedge(int u,int v,int c){
    e[++et]=(edge){v,last[u],c};last[u]=et;
    e[++et]=(edge){u,last[v],c};last[v]=et;
}

inline void getroot(int x,int fa){
    size[x]=1,f[x]=0;
    goedge(i,x)
        if (!vis[e[i].to]&&e[i].to!=fa){
            getroot(e[i].to,x);
            size[x]+=size[e[i].to];
            f[x]=max(f[x],size[e[i].to]);
        }
    f[x]=max(f[x],sum-size[x]);
    if (f[x]<f[root]) root=x;
}

void getdeep(int x,int fa){
    t[d[x]]++;
    goedge(i,x)
        if (!vis[e[i].to]&&e[i].to!=fa){
            d[e[i].to]=(d[x]+e[i].c)%3;
            getdeep(e[i].to,x);
        }
}

inline int query(int x,int c){
    t[0]=t[1]=t[2]=0;
    d[x]=c;
    getdeep(x,0);
    return t[1]*t[2]*2+t[0]*t[0];
}

void dfs(int x){
    ans+=query(x,0);
    vis[x]=1;
    goedge(i,x)
        if (!vis[e[i].to]){
            ans-=query(e[i].to,e[i].c);
            root=0;
            sum=size[e[i].to];
            getroot(e[i].to,x);
            dfs(root);
        }
}

int main(){
    n=read();
    For(i,1,n-1){
        int u=read(),v=read(),c=read()%3;
        addedge(u,v,c);
    }
    f[0]=sum=n;
    getroot(1,0);
    dfs(root);
    int g=gcd(ans,n*n);
    printf("%d/%d",ans/g,(n*n)/g);
    return 0;
}