P9988 [Ynoi2079] 2stmo

Given a rooted tree with $n$ vertices, the vertices are numbered $1,\dots,n$, where $1$ is the root. $f_2,\dots,f_n$ denote the parents of vertices $2,\dots,n$, respectively. Given $m$ pairs of integers $a_1,b_1,\dots,a_m,b_m$, you need to construct a permutation $p_1,\dots,p_m$ of $1,\dots,m$ such that the cost of this permutation does not exceed $4\times 10^9$. The cost of a permutation is defined as: $|S(a_{p_1})|+|S(b_{p_1})|+\sum\limits_{i=2}^m |S(a_{p_{i-1}})\oplus S(a_{p_i})|+|S(b_{p_{i-1}})\oplus S(b_{p_i})|$ Here, $S(x)$ is the set of vertices in the subtree rooted at $x$, $|A|$ is the number of elements in set $A$, and $A\oplus B$ is the symmetric difference of sets $A$ and $B$ (that is, the set of elements that appear in exactly one of $A$ and $B$).

The first line contains two integers $n,m$. The second line contains $n-1$ integers $f_2,\dots,f_n$. The next $m$ lines each contain two integers representing $a_i,b_i$, for $i=1,\dots,m$.

Output $m$ lines, each with one integer, representing $p_1,\dots,p_m$ in order.

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078. For $25\%$ of the testdata, $n,m\le 10^4$. For $50\%$ of the testdata, $n,m\le 2\times 10^5$. For $75\%$ of the testdata, $n,m\le 5\times 10^5$. For $100\%$ of the testdata, $1\le n,m\le 10^6$, $1\le f_i\le i-1$, $1\le a_i,b_i\le n$. Constraints. Translated by ChatGPT 5