P8214 [THUPC 2022 初赛] 赫露艾斯塔

## 提交请前往 [P8204 [Ynoi2005] tdnmo](https://www.luogu.com.cn/problem/P8204)，本题不开放提交。

给定一棵 $n$ 个顶点的有根树，顶点编号为 $1,2,\dots,n$，$1$ 号顶点为根。定义有向邻域 $N(x,y)$ 为以 $x$ 为根的子树中，距离 $x$ 小于 $y$ 的顶点构成的集合，其中 $1\le x\le n,;0\le y\le n$，$x,y$ 为整数。 给出 $m$ 个有向邻域 $N(x_i,y_i)_{i=1}^m$，你可以从 $N(1,0)$ （根据定义，这是一个空集）出发，经过不超过 $5m$ 次操作到达每个给出的有向邻域，可以使用的操作有： - 从有向邻域 $N(x,y)$ 移动到 $N(x',y')$，满足 $N(x,y)\subseteq N(x',y')$； - 撤销一次1操作，即回到之前最后一次未撤销的1操作前的位置，并将这次1操作标为已撤销； - 声明当前到达了有向邻域 $N(x_i,y_i)$，满足当前所在邻域是 $N(x_i,y_i)$； 其中操作1的代价为移动前后两个有向邻域的元素个数之差，操作2和3不计代价，要求操作2执行时必须存在未撤销的操作1，操作3必须对每个 $1\le i\le m$ 恰好各执行一次。 你需要保证操作的总代价不超过 $2.5\times{10}^{9}$。

第一行两个整数 $n\ m$； 接下来一行，共 $n-1$ 个整数，依次表示编号为 $2,3,\dots,n$ 的顶点的父亲 $f_2,\dots,f_n$，保证父亲的编号小于孩子的编号； 接下来的 $m$ 行中，第 $i$ 行两个整数 $x_i\ y_i$，表示给出的每个有向邻域。

第一行一个整数 $m'$，表示你进行的操作次数； 接下来 $m'$ 行，依次表示每个操作； 操作1表示为 $1\ x'\ y'$； 操作2表示为 $2$； 操作3表示为 $3\ i$。

【数据范围】 对于 $100%$ 的数据，满足 $1\le n,m\le 10^6$，$1\le f_i\le i-1$，$1\le x_i\le n,;0\le y_i\le n$，所有数值为整数。