点分治模板

╰半橙微兮° 2023-08-17 17:36 108阅读 0赞

debug了一晚上bug，竟然是爆了int 。再次感叹自己的码力

点分治模板，求距离在 n-L-1，n-R-2 区间内的点对数，

#include<bits/stdc++.h>
    using namespace std;
    const int M=1e5+50;
    #define ll long long
    struct Node{int to,nex;}e[M<<1];
    int n,L,R,mx,sum,rt,cnt,siz[M],head[M<<1],v[M],p[M];
    ll res;
    void add(int x,int y){
        e[cnt].to=y;e[cnt].nex=head[x];head[x]=cnt++;
        e[cnt].to=x;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(to==f||v[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,int dis,int k){
        if(dis>k)return ;
        p[++p[0]]=dis;
        for(int to,i=head[x];~i;i=e[i].nex){
            to=e[i].to;
            if(to==f||v[to])continue;
            getdis(to,x,dis+1,k);
        }
    }
    ll cal(int x,int dis,int k){
        ll ans=0;p[0]=0;
        getdis(x,-1,dis,k);
        sort(p+1,p+p[0]+1);
        for(int i=1,j=p[0];i<j;i++){
            while(p[i]+p[j]>k&&i<j)j--;
            ans+=j-i;
        }
        return ans;
    }
    void work(int x,int k){
        res+=cal(x,0,k);
        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,1,k);
            mx=0x3f3f3f3f;
            sum=siz[to];//t点
            getrt(to,-1);
            work(rt,k);
        }
    }
    
    ll slove(int k){
        if(k<=0)return 0;
        res=0;
        memset(v,0,sizeof(v));
        mx=0x3f3f3f3f;sum=n;
        getrt(1,-1);work(rt,k);
        return res;
    }
    int main(){
    //    freopen("awesome.in","r",stdin);
        int T;cin>>T;
        while(T--){
    
            memset(head,-1,sizeof(head));cnt=1;
            cin>>n>>L>>R;
            for(int x,y,i=1;i<n;i++)cin>>x>>y,add(x,y);
            cout<<slove(n-L-1)-slove(n-R-2)<<endl;
        }
        return 0;
    }