提交记录

#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
const int N = 1e5 + 10;

bool vis[N];
std::vector<int> son[N]; // 记录孩子
int rnk[N], dfn[N];
// rnk：编号->记号 dfn：记号->编号
int min[N]; // 以 N 为根节点的子树中编号最小的值
int n, q, s, cnt, dep[N], f[N][20];
std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // pq 存储记号

void dfs1(int u) {
  dep[u] = dep[f[u][0]] + 1, min[u] = u;
  for (int i = 1; i < 20; ++i) f[u][i] = f[f[u][i - 1]][i - 1];
  for (auto v : son[u]) dfs1(v), min[u] = std::min(min[u], min[v]);
}

void dfs2(int u) {
  std::sort(son[u].begin(), son[u].end(), [](int x, int y){ return min[x] < min[y]; });
  for (auto v : son[u]) dfs2(v);
  rnk[u] = ++cnt, dfn[cnt] = u;
  pq.push(rnk[u]);
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    std::cin >> f[i][0];
    if (!f[i][0]) s = i;
    else son[f[i][0]].emplace_back(i);
  }
  dfs1(1), dfs2(1);
  for (int opt, num; q; --q) {
    std::cin >> opt >> num;
    if (opt == 1) {
      for (int i = 1; i < num; ++i) vis[dfn[pq.top()]] = true, pq.pop();
      vis[dfn[pq.top()]] = true;
      std::cout << dfn[pq.top()] << '\n';
      pq.pop();
    } else {
      // 找最远的有球的祖先
      int t = num;
      for (int i = 19; ~i; --i)
        if (vis[f[t][i]]) t = f[t][i];
      pq.push(rnk[t]), vis[t] = false;
      std::cout << dep[num] - dep[t] << '\n';
    }
  }
  std::cout.flush();
  return 0;
}