思路

观察题目，我们可以发现一些性质，比如说每次操作只会撤去 $1$ 个球。

这意味着我们可以一个一个地加入球，最多只会放入 $n+q$ 个球。

然后我们观察球放下之后会落到哪里：

• 如果有多个节点选择，它会选择 以其为根节点的子树中标号最小值最小 的儿子节点。

这启发我们对于每个点将它的所有儿子按照子树中的标号最小值排序。

接下来执行一次广义上的 后序遍历，即在离开每个节点时对其进行标号。

当然，遍历时要先走排序之后靠前的儿子节点。

很显然，这样进行标号之后，一个球被放下时就会落到标号最小的没有球的点上。

怎么维护？开一个小根堆存所有没有球的节点的标号就可以了。

这样我们就成功维护好了操作 $1$。

对于操作 $2$，我们也能发现，实际上就是某个叶子节点的深度最浅的有球的祖先变为没有球。

考虑倍增，维护每个节点的 $2^i$ 级祖先。

然后开一个 $vis$ 数组，标记每个节点有没有球，这样就能找到上文所提的那个点。

最后修改这个节点的信息并把它放到堆里就可以了。

时间复杂度 $O((n+q) \log n)$。

代码

以下为代码参考。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,op,x,f[N][25],mint[N],root,wei[N],dui[N],tot;
bool vis[N];
vector<int> v[N];
priority_queue<int,vector<int>,greater<int>> pq;
bool cmp(int x,int y)
{
	return mint[x]<mint[y];
}
int dfs_pre(int now)
{
	for (int i=1;(1<<i)<=n;i++)
	{
		f[now][i]=f[f[now][i-1]][i-1];
	}
	for (int i=0;i<v[now].size();i++)
	{
		mint[now]=min(mint[now],dfs_pre(v[now][i]));
	}
	mint[now]=min(mint[now],now);
	return mint[now];
}
void dfs_wei(int now)
{
	sort(v[now].begin(),v[now].end(),cmp);
	for (int i=0;i<v[now].size();i++)
	{
		dfs_wei(v[now][i]);
	}
	wei[now]=++tot,dui[tot]=now,pq.push(wei[now]);
}
int get(int x)
{
	int ret=0;
	for (int i=20;i>=0;i--)
	{
		if (!vis[f[x][i]])continue;
		x=f[x][i];
		ret+=(1<<i);
	}
	vis[x]=0;
	pq.push(wei[x]);
	return ret;
}
int main()
{
	memset(mint,0x3f,sizeof(mint));
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&f[i][0]);
		if (f[i][0])v[f[i][0]].push_back(i);
		else root=i;
	}
	dfs_pre(root);
	dfs_wei(root);
	while (q--)
	{
		scanf("%d%d",&op,&x);
		if (op==1)
		{
			for (int i=1;i<=x;i++)
			{
				int now=pq.top();pq.pop();
				vis[dui[now]]=1;
				if (i==x)printf("%d\n",dui[now]);
			}
		}
		else
		{
			printf("%d\n",get(x));
		}
	}
	return 0;
}