题目描述

有一个装球机器，构造可以看作是一棵树。有下面两种操作：

• 从根放入一个球，只要下方有空位，球会沿着树滚下。如果同时有多个点可以走，那么会选择编号最小的节点所在路径的方向。比如依次在树根4放2个球，第一个球会落到1，第二个会落到3：
• 

 

• 从某个位置拿走一个球，那么它上方的球会落下来。比如依次拿走5, 7, 8三个球：

输入

第一行：球的个数N，操作个数Q （N, Q <= 100 000）下面N行：第i个节点的父亲。如果是根，则为0 接下来Q行：op num

1. op == 1：在根放入num个球
2. op == 2：拿走在位置num的球

输出

保证输入合法

1. op == 1：输出最后一个球落到了哪里
2. op == 2：输出拿走那个球后有多少个球会掉下来

样例输入

8 4

0

1

2

2

3

3

4

6

1 8

2 5

2 7

2 8

样例输出

1

3

2

2

这道题有两个操作，删球和加球，对于1操作，可以发现两个特性：1、对于一个节点，它下面的节点没填满，这个节点不会被填上。2、对于一个节点，它子树最小编号的子树没填满，其他子树不会被填球。那么就可以以子树最小编号的大小为顺序维护一个dfs序，在dfs序上，如果前面的位置没填满，后面的位置不会被填。如果因为删除而导致一段被填满的区间中有节点空缺，可以用小根堆(也可以优先队列)来每次取优先度最大的插入。删除操作就是删除一个节点上的球，然后这的节点到根节点链上所有球都向下落一层，也可以看作是把链上最上面有球的节点的球删掉，那么只要找到距离根最近的有球节点就行，但如果一层一层往上爬显然时间复杂度太高，所以需要倍增往上跳。

最后附上代码.

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;priority_queue< int,vector
             
              ,greater
              
                >q;vector
               
                v[200010];int n,Q;int f[20][200010];//倍增祖先int m[200010];//子树最小的编号int s[200010];//优先度int r[200010];//优先度对应节点int cnt;int root;int x,y;int opt;int d[200010];//深度int vis[200010];//是否被填标记bool cmp(int x,int y){ return m[x]
                
                 =0;i--) { if(vis[f[i][x]]==1) { x=f[i][x]; } } vis[x]=0; printf("%d\n",d[fa]-d[x]); q.push(s[x]); } }}