点分治-模板

﹏ヽ暗。殇╰゛Y 2023-06-01 06:07 21阅读 0赞

可能一步步克服恐惧的过程就是成功，所以只管面对恐惧，不思考结果，

24分钟敲模板，这是点分治第一次敲的这么顺利，纪念一下。

洛谷：2634.求距离是三的倍数的点对数

//点分治模板，找有多少点的距离是3的倍数
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int M=2e4+5;
    struct Node{int to,nex;ll v;}e[M<<1];
    int head[M<<1],cnt=1,n,siz[M],mx,rt,sum,v[M];
    ll t[4];
    void add(int x,int y,int v){
        e[cnt].to=y;e[cnt].v=v;e[cnt].nex=head[x];head[x]=cnt++;
        e[cnt].to=x;e[cnt].v=v;e[cnt].nex=head[y];head[y]=cnt++;
    }
    void getrt(int x,int f){
        siz[x]=1;int mm=0;
        for(int to,i=head[x];~i;i=e[i].nex){
            to=e[i].to;
            if(v[to]||f==to)continue;
            getrt(to,x);
            siz[x]+=siz[to];
            if(mm<siz[to])mm=siz[to];
        }
        if(mm<sum-siz[x])mm=sum-siz[x];
        if(mx>mm)mx=mm,rt=x;
    }
    void getdis(int x,int f,ll dis){
        t[dis%3]++;
        for(int to,i=head[x];~i;i=e[i].nex){
            to=e[i].to;
            if(v[to]||to==f)continue;
            getdis(to,x,dis+e[i].v);
        }
    }
    ll cal(int x,int f,int dis){
        t[0]=t[1]=t[2]=0;
        getdis(x,f,dis);
        return t[0]*t[0]+t[1]*t[2]*2;
    }
    ll slove(int x){
        ll res=cal(x,-1,0);
        v[x]=1;
        for(int to,i=head[x];~i;i=e[i].nex){
            to=e[i].to;
            if(v[to])continue;
            res-=cal(to,x,e[i].v);
            sum=siz[to];mx=0x3f3f3f3f;
            getrt(to,-1);
            res+=slove(rt);
        }
        return res;
    }
    
    int main(){
        memset(head,-1,sizeof(head));
        scanf("%d",&n);
        for(int x,y,v,i=1;i<n;i++)scanf("%d%d%d",&x,&y,&v),add(x,y,v);//建立边
        sum=n;mx=0x3f3f3f3f;
        getrt(1,-1);
        ll a=slove(rt),b=n*n;
        ll c=__gcd(a,b);
        printf("%lld/%lld",a/c,b/c);
        return 0;
    }