点分治模板-蒲公英云

点分治模板

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;
}