分析：
我们考虑，因为每次放置的时候，都是向子树中含有的编号最小的哪一个走，那么放置的顺序是固定的，我们将边以to的子树最小排序，之后得到的出栈序就是球的放入顺序。目测可以使用堆来实现，线段树也能实现，链表和并查集不能实现。
每次放球可以暴力的放入，因为满足实际不可以放入超过n个球。
每次取走的球可以通过倍增来找到，因为满足球是连续的。
附上代码：
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
#define N 100005
priority_queue<int>q;
int a[N],head[N],cnt,fa[21][N],dep[N],used[N],n,Q,vis[N],minn[N];
bool cmp(int x,int y)
{
return minn[x]<minn[y];
}
vector<int> e[N];
void dfs(int x,int from)
{
fa[0][x]=from,dep[x]=dep[from]+1;minn[x]=x;
int t=e[x].size();
for(int i=0;i<t;i++)
{
int to1=e[x][i];
if(to1!=from)
{
dfs(to1,x);
minn[x]=min(minn[x],minn[to1]);
}
}
}
int num,ans,idx[N],p[N],tims;
int get(int x)
{
int ans=0;
for(int i=19;i>=0;i--)
{
if(used[fa[i][x]])
{
ans+=(1<<i);
x=fa[i][x];
}
}
used[x]=0;
q.push(-idx[x]);
return ans;
}
void dfs1(int x,int from)
{
int t=e[x].size();
for(int i=0;i<t;i++)
{
int to1=e[x][i];
if(to1!=from)
{
dfs1(to1,x);
}
}
idx[x]=++tims;p[tims]=x;
}
int rot=0;
int main()
{
// freopen("ball.in","r",stdin);
// freopen("ball.out","w",stdout);
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
if(!x)rot=i;
else e[x].push_back(i);
q.push(-i);
}
dfs(rot,0);
for(int i=1;i<=19;i++)
{
for(int j=1;j<=n;j++)
{
fa[i][j]=fa[i-1][fa[i-1][j]];
}
}
for(int i=1;i<=n;i++)
{
if(e[i].begin()==e[i].end())continue;
sort(e[i].begin(),e[i].end(),cmp);
}
dfs1(rot,0);
while(Q--)
{
int x,y;
scanf("%d%d",&x,&y);
if(x==1)
{
int z;
while(y--)
{
z=p[-q.top()];q.pop();
used[z]=1;
}
printf("%d\n",z);
}else
{
printf("%d\n",get(y));
}
}
}