P8204 [Ynoi2005] tdnmo

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)$, you need to reach every given directed neighborhood using no more than $5m$ operations. The allowed operations are: 1. Move from a directed neighborhood $N(x,y)$ to $N(x',y')$, such that $N(x,y)\subseteq N(x',y')$. 2. Undo one operation of type 1, i.e., return to the position before the most recent not-yet-undone type 1 operation, and mark that type 1 operation as undone. 3. Declare that you have currently reached the directed neighborhood $N(x_i,y_i)$, where your current neighborhood equals $N(x_i,y_i)$. For operation 1, the cost is the difference between the sizes (number of elements) of the two directed neighborhoods before and after the move. Operations 2 and 3 have no cost. When performing operation 2, there must exist a type 1 operation 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, which are 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. The next $m$ lines each contain two integers $x_i\ y_i$. Line $i$ describes the 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$.

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078, SPJ: nalemy. 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$. All values are integers. Translated by ChatGPT 5