题目

这里写图片描述

分析

首先预处理出每个点的优先级，当有一个人进入时，一定会走到优先级最大的空房间中。

把所有空的房间扔到一个堆中，按优先级大小维护这个堆。

答案怎么求就不说了，很容易想到，就只讲操作吧。

对于第一种操作，我们就将一个一个扔进优先级最大的房间（即堆顶），因为堆顶的房间有人，所以将堆顶的房间踢出堆。

对于第二种操作，当一个房间空了，一定是从它的父亲房间补上来。

倍增将深度最大的空了的房间的祖宗取出来，因为它的祖宗们一定一个接一个往下走一个位置。

也就是说，深度最大的空了的房间的祖宗人的人会走掉，那么将这个房间加入堆。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           const int maxlongint=2147483647;const int mo=1000000007;const int N=110005;using namespace std;struct ddx{ int x,y;}a[N*2];int last[N*4],next[N*4],to[N*4],sum,n,m,t,ans,b[N*2],tot,belong[N*2];int heap[N*2],th[N*2],g[N*2][20],tot1,deep[N*2];bool bz[N*2];bool cmp(ddx x,ddx y){ return x.x
           
            th[heap[x]] && x!=1) { belong[heap[x]]=x/2; belong[heap[x/2]]=x; heap[x]=heap[x]^heap[x/2]; heap[x/2]=heap[x]^heap[x/2]; heap[x]=heap[x]^heap[x/2]; x/=2; }}int down(int x){ while((th[heap[x]]>th[heap[x*2]] || th[heap[x]]>th[heap[x*2+1]]) && x*2<=sum) { if(x*2+1>sum && th[heap[x]]
            
             sum) { belong[heap[x]]=x*2; belong[heap[x*2]]=x; heap[x]=heap[x]^heap[x*2]; heap[x*2]=heap[x]^heap[x*2]; heap[x]=heap[x]^heap[x*2]; x=x*2; } else { belong[heap[x]]=x*2+1; belong[heap[x*2+1]]=x; heap[x]=heap[x]^heap[x*2+1]; heap[x*2+1]=heap[x]^heap[x*2+1]; heap[x]=heap[x]^heap[x*2+1]; x=x*2+1; } }}int insert(int x){ heap[++sum]=x; belong[x]=sum; up(sum);}int cut(){ belong[heap[sum]]=1; belong[heap[1]]=0; heap[1]=heap[sum--]; heap[sum+1]=0; down(1);}void dg(int x){ deep[x]=deep[g[x][0]]+1; for(int i=b[x];a[i].x==x;i++) { if(a[i].y!=g[x][0]) { g[a[i].y][0]=x; bj(x,a[i].y); dg(a[i].y); } } th[x]=++tot1; insert(x);}int lca(int x){ int num=x; for(int i=log2(n);i>=0;i--) if((!belong[g[x][i]]) && g[x][i]) x=g[x][i]; if((!belong[g[x][0]]) && g[x][0]) x=g[x][0]; printf("%d\n",deep[num]-deep[x]); return x;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n-1;i++) { scanf("%d%d",&a[i].x,&a[i].y); a[n+i-1].x=a[i].y; a[n+i-1].y=a[i].x; } sort(a+1,a+n*2-1,cmp); for(int i=1;i<=n*2-2;i++) if(a[i].x!=a[i-1].x) b[a[i].x]=i; dg(1); for(int i=1;i<=log2(n);i++) for(int j=1;j<=n;j++) g[j][i]=g[g[j][i-1]][i-1]; for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); if(x==1) { for(int j=1;j<=y;j++) { if(j==y) printf("%d\n",heap[1]); cut(); } } else { insert(lca(y)); } }}