structHeal{    priority_queue
     
       real;    priority_queue
      
        stack;    void push(int x){        real.push(x);    }    void pop(int x){        stack.push(x);    }    int top(){        while(real.empty()==0&&stack.empty()==0&&real.top()==stack.top())         real.pop(),stack.pop();        if(real.empty())return0;        return real.top();    }}
      
     

 

这样打堆虽然方便但是top到最后大约有6，7的常数。

今天考试卡常卡的怀疑人生……..这个故事告诉我们千万不要忘了常数分析..........

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define MAXN 1000010using namespace std;inline int read(){ int sum=0; char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9') { sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar(); } return sum;}struct ScapeGoat_Tree{ struct node { node *ch[2]; int key,size,cover,ex; void update() { size=ch[0]->size+ch[1]->size+ex; cover=ch[0]->cover+ch[1]->cover+1; } bool bad() { return ch[0]->cover>=cover*0.756+5||ch[1]->cover>=cover*0.756+5; } }Mem[MAXN],*null,*root,*stack[MAXN],*lst[MAXN]; int len,top; void Init() { root=null=Mem; null->size=null->cover=null->ex=0; null->ch[0]=null->ch[1]=Mem; for(int i=1;i
           
            ch[0]=t->ch[1]=null; t->size=t->cover=t->ex=1; t->key=key; return t; } void travel(node *p) { if(p==null)return; travel(p->ch[0]); if(p->ex)lst[++len]=p; else stack[++top]=p; travel(p->ch[1]); } node *divide(int l,int r) { if(l>r)return null; int mid=(l+r)>>1; lst[mid]->ch[0]=divide(l,mid-1); lst[mid]->ch[1]=divide(mid+1,r); lst[mid]->update(); return lst[mid]; } void rebuild(node *&p) { len=0; travel(p); p=divide(1,len); } node **insert(node *&p,int key) { if(p==null) { p=New(key); return &null; } p->size++; p->cover++; node **ret=insert(p->ch[p->key<=key],key); if(p->bad())ret=&p; return ret; } void erace(node *p,int k) { p->size--; if(p->ex&&k==p->ch[0]->size+1) { p->ex=0; return; } if(k<=p->ch[0]->size)erace(p->ch[0],k); else erace(p->ch[1],k-p->ch[0]->size-p->ex); } int Kth(int k) { node *p=root; while(p!=null) { if(p->ex&&k==p->ch[0]->size+1)return p->key; else if(p->ch[0]->size>=k)p=p->ch[0]; else k-=p->ch[0]->size+p->ex,p=p->ch[1]; } } int Rank(int x) { node *p=root; int ret=1; while(p!=null) if(p->key>=x) p=p->ch[0]; else ret+=p->ch[0]->size+p->ex,p=p->ch[1]; return ret; } void Insert(int x) { node **p=insert(root,x); if(*p!=null)rebuild(*p); } void Erace_kth(int k) { erace(root,k); if(root->size
            
             cover*0.756)rebuild(root); } void Erace(int x) { Erace_kth(Rank(x)); }}YY;inline int Max(int x,int y){ return x>y?x:y;}inline int Abs(int x){ return x<0?0-x:x;}int n,m;struct Tr{ int to,next,w;}c[MAXN<<1];int head[MAXN],t;int f[MAXN];inline void add(int x,int y,int z){ c[++t].to=y; c[t].w=z; c[t].next=head[x]; head[x]=t;}int A[MAXN];bool mark[MAXN];int q[MAXN],top,tail,one,two;inline void bfs1(){ memset(mark,0,sizeof(mark)); memset(A,0,sizeof(A)); q[1]=1; top=tail=1; int now=0; one=1; mark[1]=1; while(top<=tail) { int x=q[top++]; if(A[x]>now) { one=x; now=A[x]; } for(int i=head[x];i;i=c[i].next) if(mark[c[i].to]==0) { mark[c[i].to]=1; q[++tail]=c[i].to; A[c[i].to]=A[x]+c[i].w; } }}inline void bfs2(){ memset(mark,0,sizeof(mark)); memset(A,0,sizeof(A)); q[1]=one; top=tail=1; int now=0; two=one; mark[one]=1; while(top<=tail) { int x=q[top++]; if(A[x]>now) { two=x; now=A[x]; } for(int i=head[x];i;i=c[i].next) if(mark[c[i].to]==0) { mark[c[i].to]=1; q[++tail]=c[i].to; A[c[i].to]=A[x]+c[i].w; } }}inline void bfs3(){ memset(mark,0,sizeof(mark)); memset(A,0,sizeof(A)); q[1]=one; top=tail=1; mark[one]=1; while(top<=tail) { int x=q[top++]; for(int i=head[x];i;i=c[i].next) if(mark[c[i].to]==0) { mark[c[i].to]=1; q[++tail]=c[i].to; A[c[i].to]=A[x]+c[i].w; } }}int B[MAXN];inline void bfs4(){ memset(mark,0,sizeof(mark)); q[1]=two; top=tail=1; mark[two]=1; while(top<=tail) { int x=q[top++]; for(int i=head[x];i;i=c[i].next) if(mark[c[i].to]==0) { mark[c[i].to]=1; q[++tail]=c[i].to; B[c[i].to]=B[x]+c[i].w; } }}inline void Init(){ n=read(),m=read(); m=Abs(m); YY.Init(); for(int i=2;i<=n;i++) { int x=read(),y=read(); add(x,i,y); add(i,x,y); } bfs1(),bfs2(),bfs3(),bfs4(); for(int i=1;i<=n;i++)A[i]=Max(A[i],B[i]);}inline bool jud(int p){ int x=YY.Kth(1),y=YY.Kth(YY.root->size); if(Abs(x-p)>m||Abs(y-p)>m)return 0; return 1;}inline void work(){ top=1; int ans=1; YY.Insert(A[1]); for(int i=2;i<=n;i++) { while(top!=i&&!jud(A[i])) YY.Erace(A[top]),top++; YY.Insert(A[i]); ans=Max(ans,YY.root->size); } printf("%d",ans);}int main(){ //freopen("race.in","r",stdin); //freopen("race.out","w",stdout); Init(); work(); return 0;}