P9999 [Ynoi2000] tmostnrq2

Given a tree with $n$ vertices, labeled $1,\dots,n$, and a sequence $a_1,\dots,a_{n_0}$ of length $n_0$. There are $m$ queries. Each query gives $l,r,x$. Starting from vertex $x$, move one step toward $a_l,\dots,a_r$ in order, and output the vertex you finally reach. If $x=y$, then moving one step from vertex $x$ toward $y$ still stays at $x$. Otherwise, you move to the vertex that is adjacent to $x$ on the tree and is closest to $y$.

The first line contains three integers $n,n_0,m$. The next line contains $n-1$ integers, representing $f_2,\dots,f_n$ in order, where $f_i$ is the parent of vertex $i$, and $1$ is the root. The next line contains $n_0$ integers, representing $a_1,\dots,a_{n_0}$ in order. The next $m$ lines each contain three integers $l,r,x$, describing one query.

Output $m$ lines. Each line is the answer to the corresponding query.

Idea: Ynoi, Solution: zhoukangyang & ccz181078, Code: zhoukangyang, Data: ccz181078. Constraints: For $100\%$ of the testdata, $1\le n,n_0,m\le 10^6$. Translated by ChatGPT 5