BallMachine.cpp

#include <bits/stdc++.h>
using namespace std;

const int MAX = 100005;
const int INF = 1000000000;
const int  LN = 20;

int P[MAX], DP[MAX][LN], VAL[MAX], MN[MAX], F[MAX], N, Q;
vector < int > adjList[MAX];
int root = 0, cur_time = 0;

struct node{
	int id;
	node(int temp_id = 0){
		id = temp_id;
	}
	friend bool operator < (node x, node y){
		return (VAL[x.id] < VAL[y.id]);
	}
};

set < node > nodes;

void dfs_init(int u, int p){
	MN[u] = u;
	for(auto v : adjList[u]){
		if(v == p) continue;
		dfs_init(v, u);
		MN[u] = min(MN[u], MN[v]);
	}
}

void dfs_order(int u, int p){
	for(int i = 1; i < LN; i++){
		DP[u][i] = DP[DP[u][i - 1]][i - 1];
	}
	
	for(auto v : adjList[u]){
		if(v == p) continue;
		DP[v][0] = u;
		dfs_order(v, u);
	}
    
        VAL[u] = F[u] = ++cur_time;
        nodes.insert(node(u));
}

inline bool cmp(int x, int y){
	return (MN[x] < MN[y]);
}

int main(){
		
	scanf("%d %d\n", &N, &Q);
	
	for(int i = 1; i <= N; i++){
		scanf("%d\n", &P[i]);
		if(P[i] == 0) root = i;
		else{
			adjList[i].push_back(P[i]);
			adjList[P[i]].push_back(i);
		}
	}

	DP[root][0] = 0;

	dfs_init(root, -1);
	for(int i = 1; i <= N; i++) sort(adjList[i].begin(), adjList[i].end(), cmp);
	dfs_order(root, -1);
	
	while(Q--){
		int type, x;
		scanf("%d %d\n", &type, &x);
		if(type == 1){
			// Add (x) balls
			node cur;
			for(int i = 0 ; i < x ; i++){
				cur = *nodes.begin();
				nodes.erase(cur);
				VAL[cur.id] = INF;
				nodes.insert(cur);
			}
			printf("%d\n", cur.id);
		}
		else{
			// Remove ball from node (x)
			int res = 0, cur = x;
			for(int i = LN - 1 ; i >= 0 ; i--){
				int p = DP[cur][i];
				if( (p) && (VAL[p] == INF) ) 
					cur = p, res += (1 << i);
			}
			printf("%d\n", res);
			nodes.erase(node(cur));
			VAL[cur] = F[cur];
			nodes.insert(node(cur));
		}
	}
}