[LUOGU] P2634 [国家集训队]聪聪可可

点分治裸题，甚至不需要栈回撤。

尝试用容斥写了一波，就是把所有子树混一块计算，最后减去子树内路径条数。

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

inline int rd(){

    int ret=,f=;char c;

    while(c=getchar(),!isdigit(c))f=c=='-'?-:;

    while(isdigit(c))ret=ret*+c-'',c=getchar();

    return ret*f;

}

const int MAXN=;

struct Edge{

    int next,to,w;

}e[MAXN<<];

int ecnt,head[MAXN];

inline void add(int x,int y,int w){

    e[++ecnt].next = head[x];

    e[ecnt].to = y;

    e[ecnt].w = w;

    head[x] = ecnt;

}

int n,m;

bool vis[MAXN];

int siz[MAXN];

void getsiz(int x,int pre){

    siz[x]=;

    for(int i=head[x];i;i=e[i].next){

        int v=e[i].to;

        if(vis[v]||v==pre) continue;

        getsiz(v,x);

        siz[x]+=siz[v];

    }

}

int root,mn;

void getroot(int x,int pre,int tot){

    int mx=;

    for(int i=head[x];i;i=e[i].next){

        int v=e[i].to;

        if(vis[v]||v==pre) continue;

        mx=max(mx,siz[v]);

        getroot(v,x,tot);

    }

    mx=max(mx,tot-siz[x]);

    if(mx<mn) mn=mx,root=x;

}

int f[];

int s[MAXN];

void dfs(int x,int pre,int dis){

    s[++s[]]=dis%;

    for(int i=head[x];i;i=e[i].next){

        int v=e[i].to;

        if(vis[v]||v==pre) continue;

        dfs(v,x,(dis+e[i].w)%);

    }

}

long long ans=;

void dac(int x){

    mn=n;f[]=;

    getsiz(x,-);

    getroot(x,-,siz[x]);

    int u=root;vis[u]=;

    int offset=;

    for(int i=head[u];i;i=e[i].next){

        int v=e[i].to;

        if(vis[v]) continue;

        s[]=;dfs(v,u,e[i].w%);

        int t0=,t1=,t2=;

        for(int j=s[];j>=;j--){

            if(s[j]==) t0++;

            if(s[j]==) t1++;

            if(s[j]==) t2++;

        }

        offset+=t0*t0+*t1*t2;

        for(int j=s[];j>=;j--){

            f[s[j]]++;

        }

    }

    ans+=f[]*f[]+*f[]*f[]-offset;

    memset(f,,sizeof(f));

    for(int i=head[u];i;i=e[i].next){

        int v=e[i].to;

        if(!vis[v]) dac(v);

    }

}

long long gcd(long long x,long long y){

    return !y?x:gcd(y,x%y);

}

int main(){

    n=rd();

    int x,y,w;

    for(int i=;i<=n-;i++){

        x=rd();y=rd();w=rd();

        add(x,y,w%);add(y,x,w%);

    }

    dac();

    long long tmp=1ll*n*n;

    long long G=gcd(tmp,ans);

    printf("%lld/%lld",ans/G,tmp/G);

    return ;

}