點分治板子_精品.doc

點分治 例題1: 一棵n個點的有邊權的樹，問你滿足x到y距離小于等于k的無序點對(x,y)的個數是多少(poj1741) typedef long long ll; const int N=2e4+5; const int inf=0x3f3f3f3f; struct Edge { int u,v,w,next; }edges[N]; int head[N],cnt; int sz[N],vis[N],root,mx,len; int q[N],r,d[N]; int k; void addEdge(int u,int v,int w) { edges[cnt].u=u; edges[cnt].v=v; edges[cnt].w=w; edges[cnt].next=head[u]; head[u]=cnt++; } void findrt(int u,int fa) { sz[u]=1; int ma=0; for(int i=head[u];~i;i=edges[i].next) { int v=edges[i].v; if(v==fa||vis[v])continue; findrt(v,u); sz[u]+=sz[v]; ma=max(ma,sz[v]); } ma=max(ma,len-sz[u]); if(ma<mx) { mx=ma; root=u; } } void getdis(int u,int fa) { q[++r]=d[u]; for(int i=head[u];~i;i=edges[i].next) { int v=edges[i].v; if(v==fa||vis[v])continue; d[v]=d[u]+edges[i].w; getdis(v,u); } } ll solve(int u,int val) { r=0; d[u]=val; getdis(u,0); ll sum=0,l=1; sort(q+1,q+1+r); while(l<r) { if(q[l]+q[r]<=k) { sum+=r-l; l++; } else r--; } return sum; } ll ans; void divide(int u) { ans+=solve(u,0); vis[u]=1; for(int i=head[u];~i;i=edges[i].next) { int v=edges[i].v; if(vis[v])continue; ans-=solve(v,edges[i].w); mx=inf; len=sz[v]; findrt(v,0); divide(root); } } int main() { int n; while(scanf("%d%d",&n,&k)) { if(n+k==0)break; cnt=0; for(int i=0;i<=n;i++) { head[i]=-1; vis[i]=0; } for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addEdge(u,v,w); addEdge(v,u,w); } ans=0; len=n; mx=inf; findrt(1,0); divide(root); printf("%lld\n",ans); } return 0; } 例題2: 一棵n個點的有邊權的樹，問你滿足x到y距離%3==0的無