BZOJ 3365 路程统计
嗯由于上次邱老师来讲课考了一道点分治，看出来了但不会写，后悔至今，所以就写了一道点分裸题达成今年第一个计划，（居然是一发过还开心了一把）
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=100000+5;
int siz,ecnt,ms[INF],size[INF],k,n,G[INF],s[INF],dis[INF];
bool used[INF];
struct edge{
int to,next,val;
} e[2*INF];
void add(int x,int y,int val){
e[++ecnt].to=y;
e[ecnt].next=G[x];
e[ecnt].val=val;
G[x]=ecnt;
}
void pre(){
int m,x,y,z;
char w;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d%d %c",&x,&y,&z,&w);
add(x,y,z);
add(y,x,z);
}
scanf("%d",&k);
}
int get_ans(int x,int D){
/*printf("%d\n",x);
for(int i=1;i<=s[0];++i) printf("%d ",s[i]);
printf("\n");*/
int l=1,r=1;
int ans=0;
sort(s+1,s+s[0]+1);
while(l<=r&&r<=s[0]){
int lef=D-s[l];
while(s[r+1]<=lef&&r+1<=s[0]) r++;
while(s[r]>lef&&l<r) r--;
ans+=r-l;
l++;
}
//printf("the answer is:%d\n",ans);
return ans;
}
int getsize(int x,int last){
size[x]=1;
for(int i=G[x];i;i=e[i].next){
int v=e[i].to;
if(used[v]||v==last) continue;
size[x]+=getsize(v,x);
}
return size[x];
}
int rooty(int x,int last){
ms[x]=siz-size[x];
int ret=x;
for(int i=G[x];i;i=e[i].next){
int v=e[i].to;
if(used[v]||v==last) continue;
ms[x]=max(ms[x],size[v]);
}
for(int i=G[x];i;i=e[i].next){
int v=e[i].to;
if(used[v]||v==last) continue;
int u=rooty(v,x);
if(ms[u]<ms[ret]) ret=u;
}
return ret;
}
void get_dis(int x,int last){
s[++s[0]]=dis[x];
for(int i=G[x];i;i=e[i].next){
int v=e[i].to;
if(used[v]||v==last) continue;
dis[v]=dis[x]+e[i].val;
get_dis(v,x);
}
}
int cut(int x){
int ans=0;
siz=getsize(x,-1);//find the size of this tree
int rem=rooty(x,-1);//find the root of this tree
//printf("%d %d %d\n",x,rem,siz);
dis[rem]=0;
s[0]=0;
get_dis(rem,-1);//find the dis of every son of this tree and put them into s
ans+=get_ans(rem,k);//get all of dis(i)+dis(j)<=k
used[rem]=true;
for(int i=G[rem];i;i=e[i].next){//keep away from which are in the same subtree but I counted
s[0]=0;
int v=e[i].to;
if(used[v]) continue;
dis[v]=e[i].val;
get_dis(v,-1);
ans-=get_ans(v,k);
}
for(int i=G[rem];i;i=e[i].next){//solve the others
int v=e[i].to;
if(used[v]) continue;
ans+=cut(v);
}
return ans;
}
int main(){
freopen("dis.in","r",stdin);
freopen("dis.out","w",stdout);
pre();
printf("%d\n",cut(1));
return 0;
}