P8214 [THUPC 2022 Preliminary] Heru Aisita

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

Please submit at [P8204 [Ynoi2005] tdnmo](https://www.luogu.com.cn/problem/P8204). This problem does not accept submissions. Given a rooted tree with $n$ vertices numbered $1,2,\dots,n$, where vertex $1$ is the root. Define the directed neighborhood $N(x,y)$ as the set of vertices in the subtree rooted at $x$ whose distance to $x$ is less than $y$, where $1\le x\le n,\;0\le y\le n$, and $x,y$ are integers. You are given $m$ directed neighborhoods $N(x_i,y_i)_{i=1}^m$. Starting from $N(1,0)$ (by definition, this is an empty set), you need to reach each given directed neighborhood using at most $5m$ operations. The allowed operations are: - Move from directed neighborhood $N(x,y)$ to $N(x',y')$, satisfying $N(x,y)\subseteq N(x',y')$. - Undo one operation 1, that is, return to the position before the most recent operation 1 that has not been undone, and mark that operation 1 as undone. - Declare that you have currently reached directed neighborhood $N(x_i,y_i)$, satisfying that your current neighborhood is exactly $N(x_i,y_i)$. The cost of operation 1 is the difference between the sizes of the two directed neighborhoods before and after the move. Operations 2 and 3 have no cost. For operation 2, there must exist an operation 1 that has not been undone. Operation 3 must be performed exactly once for each $1\le i\le m$. You must ensure that the total cost of all operations does not exceed $2.5\times{10}^{9}$.

The first line contains two integers $n\ m$. The next line contains $n-1$ integers, describing the parents $f_2,\dots,f_n$ of vertices $2,3,\dots,n$ in order. It is guaranteed that the parent index is smaller than the child index. In the following $m$ lines, the $i$-th line contains two integers $x_i\ y_i$, representing each given directed neighborhood.

The first line contains an integer $m'$, the number of operations you perform. The next $m'$ lines describe each operation in order. Operation 1 is written as $1\ x'\ y'$. Operation 2 is written as $2$. Operation 3 is written as $3\ i$.

Constraints For $100\%$ of the testdata, $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$, and all values are integers. Translated by ChatGPT 5