[IOI2011]Race

点分治板子题。

直接点分治统计，统计的时候开个桶维护下就好了。

注(tiao)意(le)细(hen)节(jiu)。

#include
    
     #include
     
      #include
      
       #define R register#define I inlineusing namespace std;const int S=200003,N=400003,K=1000003,inf=0x3f3f3f3f;char buf[1000000],*p1,*p2;I char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,S,stdin),p1==p2)?EOF:*p1++;}I int rd(){    R int f=0; R char c=gc();    while(c<48||c>57) c=gc();    while(c>47&&c<58) f=f*10+(c^48),c=gc();    return f;}struct D{int l,d;}p[S];int h[S],s[N],g[N],w[N],t[S],v[S],q[S],a[K],c,n,k,u,r,e,o;I int min(int x,int y){return x
       
        y?x:y;}I void add(int x,int y,int z){s[++c]=h[x],h[x]=c,g[c]=y,w[c]=z;}void gts(int x,int f){t[x]=1;    for(R int i=h[x],y;i;i=s[i]) if(!v[y=g[i]]&&y^f) gts(y,x),t[x]+=t[y];}void gtr(int x,int f,int a){R int i,y,m=0;    for(i=h[x];i;i=s[i]) if(!v[y=g[i]]&&y^f) gtr(y,x,a),m=max(m,t[y]);    m=max(m,a-t[x]); if(m
        
         k) return ; p[++e]=(D){l,d},q[++q[0]]=d;    for(R int i=h[x],y;i;i=s[i]) if(!v[y=g[i]]&&y^f) dfs(y,x,l+1,d+w[i]);}void dac(int x){R int i,j,y;    for(q[0]=0,u=n,gts(x,0),gtr(x,0,t[x]),v[r]=1,a[0]=0,i=h[r];i;i=s[i])        if(!v[y=g[i]]){e=0,dfs(y,r,1,w[i]);            for(j=1;j<=e;++j) o=min(o,p[j].l+a[k-p[j].d]);            for(j=1;j<=e;++j) a[p[j].d]=min(a[p[j].d],p[j].l);        }    for(i=1;i<=q[0];++i) a[q[i]]=inf;    for(i=h[r];i;i=s[i]) if(!v[y=g[i]]) dac(y);}int main(){    R int i,x,y,z;    for(n=rd(),k=rd(),i=1;i