题目描述
有一个装球机器，构造可以看作是一棵树。有下面两种操作：
- 从根放入一个球，只要下方有空位，球会沿着树滚下。如果同时有多个点可以走，那么会选择编号最小的节点所在路径的方向。比如依次在树根
4放2个球，第一个球会落到1，第二个会落到3：
- 从某个位置拿走一个球，那么它上方的球会落下来。比如依次拿走
5, 7, 8三个球：
输入
第一行：球的个数N，操作个数Q （N, Q <= 100 000）下面N行：第i个节点的父亲。如果是根，则为0 接下来Q行：op num
-
op == 1：在根放入num个球 -
op == 2：拿走在位置num的球
输出
保证输入合法
-
op == 1：输出最后一个球落到了哪里 -
op == 2：输出拿走那个球后有多少个球会掉下来
样例输入
8 4
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8
样例输出
1
3
2
2
3
2
2
这道题有两个操作，删球和加球，对于1操作，可以发现两个特性：1、对于一个节点，它下面的节点没填满，这个节点不会被填上。2、对于一个节点，它子树最小编号的子树没填满，其他子树不会被填球。那么就可以以子树最小编号的大小为顺序维护一个dfs序，在dfs序上，如果前面的位置没填满，后面的位置不会被填。如果因为删除而导致一段被填满的区间中有节点空缺，可以用小根堆(也可以优先队列)来每次取优先度最大的插入。删除操作就是删除一个节点上的球，然后这的节点到根节点链上所有球都向下落一层，也可以看作是把链上最上面有球的节点的球删掉，那么只要找到距离根最近的有球节点就行，但如果一层一层往上爬显然时间复杂度太高，所以需要倍增往上跳。
最后附上代码.
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
priority_queue< int,vector<int>,greater<int> >q;
vector<int>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]<m[y];
}
void dfs(int x)//按子树最小编号大小排序并处理深度
{
m[x]=x;
for(int i=0;i<v[x].size();i++)
{
f[0][v[x][i]]=x;
d[v[x][i]]=d[x]+1;
dfs(v[x][i]);
m[x]=min(m[x],m[v[x][i]]);
}
sort(&v[x][0],&v[x][v[x].size()],cmp);
}
void getsign(int x)//处理优先度
{
for(int i=0;i<v[x].size();i++)
{
getsign(v[x][i]);
}
s[x]=++cnt;
r[cnt]=x;
}
int main()
{
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
if(x==0)
{
root=i;
}
else
{
v[x].push_back(i);
}
}
for(int i=1;i<=n;i++)
{
q.push(i);
}
d[root]=1;
dfs(root);
getsign(root);
for(int i=1;i<=20;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][f[i-1][j]];
}
}
while(Q--)
{
scanf("%d%d",&opt,&x);
if(opt==1)
{
while(x--)
{
y=r[q.top()];
q.pop();
vis[y]=1;
}
printf("%d\n",y);
}
else
{
int fa=x;
for(int i=20;i>=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]);
}
}
}