分治算法-蒲公英云

分治算法

可能我太菜了，众多题解的t0*t0 +t1*t2*2始终没看懂

分治大模拟好！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const int M=20010;
struct Node{ int next,to,w;}e[M*2];
int n,head[M*2],siz[M],cnt,sum,mp,rt,v[M],dis[M],judge[5];
ll res=0,ans=0,tem;
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    return b?gcd(b,a%b):a;
}
void add(int x,int to,int w){
    e[cnt].to=to;
    e[cnt].w=w;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void getrt(int x,int fa){
    siz[x]=1;
    int mm=0;
    for(int to,i=head[x];~i;i=e[i].next){
        to=e[i].to;
        if(v[to]||fa==to)continue;
        getrt(to,x);
        siz[x]+=siz[to];
        mm=max(mm,siz[to]);
    }
    mm=max(sum-siz[x],mm);
    if(mp>mm)mp=mm,rt=x;
}
void dfs(int x,int fa){
    siz[x]=1;
    int mm=0;
    for(int to,i=head[x];~i;i=e[i].next){
        to=e[i].to;
        if(v[to]||fa==to)continue;
        dfs(to,x);
        siz[x]+=siz[to];
    }
}
void getdis(int x,int fa,int w){
     for(int to,i=head[x];~i;i=e[i].next){
        to=e[i].to;
        if(v[to]||to==fa)continue;
        dis[++dis[0]]=(e[i].w+w)%3;
        getdis(to,x,dis[dis[0]]);
    }
}
void work(int x){
    v[x]=1;
    judge[0]=1;
    for(int to,i=head[x];~i;i=e[i].next){
        to=e[i].to;
        if(v[to])continue;
        dis[dis[0]=1]=e[i].w;
        getdis(to,x,dis[dis[0]]);
        for(int j=dis[0];j;j--)res+=judge[(3-dis[j])%3];
        for(int j=dis[0];j;j--)judge[dis[j]]++;
    }
    memset(judge,0,sizeof(judge));
}
void slove(int x){
    work(x);
    for(int to,i=head[x];~i;i=e[i].next){
        to=e[i].to;
        if(v[to])continue;
        sum=siz[to];mp=INF;
        getrt(to,0);
        dfs(rt,0);
        slove(rt);
    }
}
int main(){
    cnt=1;memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int x,y,z,i=1;i<n;i++){
        scanf("%d%d%d",&x,&y,&z);
        z%=3;
        add(x,y,z);
        add(y,x,z);
    }
    mp=INF;sum=n;
    getrt(1,0);
    dfs(rt,0);
    slove(rt);
    res=res+res+n;
    ans=n*n;
    tem=gcd(ans,res);
    cout<<res/tem<<"/"<<ans/tem;
    return 0;
}