Steven_Meng's Blog

传送门

一道非常模板的点分治，核心函数是$Calc()$，返回当前子树中，经过根节点的链有多少条长度是$3$的倍数，实现时，记录$f_0,f_1,f_2$，分别代表有多少条以根节点为端点的链长度$\mod 3=0,1,2$，最后乘法原理相乘即可。

注意容斥原理，要减去两条链共用一条根节点发出的边的情况，如图中红蓝两条链：

#include <bits/stdc++.h>
#define MAXN 20005
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<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
struct node{
    int to,len;
};
vector<node>G[MAXN];
inline void AddEdge(int u,int v,int w){
    G[u].push_back(node{v,w});
}
int sz[MAXN],f[MAXN],root;
int vis[MAXN];
//sz是有向的子树的大小，f是无向的子树的最大值，root为重心
void GetRoot(int u,int father,int tot){
    sz[u]=1,f[u]=0;
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i].to;
        if (v!=father&&!vis[v]){
            GetRoot(v,u,tot);
            sz[u]+=sz[v];
            f[u]=max(f[u],sz[v]);
        }
    }
    f[u]=max(f[u],tot-sz[u]);
    if (f[u]<f[root]) root=u;
}
int ha[3];
void GetDep(int u,int father,int dep){
    ha[dep]++;
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i].to,w=G[u][i].len;
        if (v!=father&&!vis[v]){
            GetDep(v,u,(dep+w)%3);
        }
    }
}
inline int Calc(int u,int w){
    ha[0]=ha[1]=ha[2]=0;
    GetDep(u,0,w);
    return ha[1]*ha[2]*2+ha[0]*ha[0];//1和2可以互相交换，所以两种情况
}
inline void NewRoot(int u,int sz){//将root赋值为以u为根节点的子树(大小sz)的重心
    root=0;
    GetRoot(u,0,sz);
}
int ans;
void dfs(int u){
    ans+=Calc(u,0);
    vis[u]=true;
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i].to,w=G[u][i].len;
        if (!vis[v]){
            ans-=Calc(v,w);//容斥
            NewRoot(v,sz[v]);
            dfs(root);
        }
    }
}

int gcd(int x,int y){
    return x%y==0?y:gcd(y,x%y);
}
int main(){
    int n=read();
    for (register int i=1;i<n;++i){
        int u=read(),v=read(),w=read()%3;
        AddEdge(u,v,w);
        AddEdge(v,u,w);
    }
    f[0]=n;
    NewRoot(1,n);
    dfs(root);
    int g=gcd(ans,n*n);
    printf("%d/%d\n",ans/g,n*n/g);
}