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