点分治

今天学的算法，呀。其实之前打比赛时做到过类似的题目。
当时没有去补题，感觉怪难的。现在学学。

点分治主要是用于求解树上路径类的问题。
这题如果能想到点分治的话，思路其实还是挺清晰的。
但是，刚学，我板子写错了哦

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+100;
const int inf=1e9;
struct edge{
    int to,cost,next;
}E[N<<1];
int head[N];
int cnt=1;
void add(int from,int to,int cost){
    E[cnt].to=to;E[cnt].cost=cost;
    E[cnt].next=head[from];
    head[from]=cnt++;
}

int root;
int maxson[N],size[N];
int sig;
bool vis[N];

void getroot(int u,int fa){
    size[u]=1;maxson[u]=0;
    for (int i=head[u];i;i=E[i].next){
        int v=E[i].to;int cost=E[i].cost;
        if (vis[v]||v==fa)continue;
        getroot(v,u);
        size[u]+=size[v];
        maxson[u]=max(maxson[u],size[v]);
    }maxson[u]=max(maxson[u],sig-size[u]);
    if(maxson[u]<maxson[root])root=u;
}
ll res[3];
void getrood(int u,int fa,ll len){
    res[len%3]++;
    for (int i=head[u];i;i=E[i].next){
        int v=E[i].to;int cost=E[i].cost;
        if (vis[v]||v==fa)continue;
        getrood(v,u,len+cost);
    }
}

ll Solve(int u,ll len){
    res[0]=res[1]=res[2]=0;
    getrood(u,0,len);
    return res[0]*res[0]+res[1]*res[2]*2;
}

ll ans=0;
void dfs(int u){
    vis[u]=1;
    ans+=Solve(u,0);
    for (int i=head[u];i;i=E[i].next){
        int v=E[i].to;int cost=E[i].cost;
        if (vis[v])continue;
        ans-=Solve(v,cost);
        root=0;sig=size[v];
        getroot(v,u);
        dfs(root);
    }
}

int n;

int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for (int i=1,u,v,w;i<n;++i){
        cin>>u>>v>>w;w%=3;
        add(u,v,w);add(v,u,w);
    }
    sig=n;root=0;
    maxson[0]=inf;
    getroot(1,0);
    dfs(root);
    ll c=__gcd(ans,(ll)n*(ll)n);
    cout<<ans/c<<"/"<<(ll)n*(ll)n/c<<endl;
}