Technocup 2022 - Elimination Round 3 |
---|
Finished |
Petya has a rooted tree with an integer written on each vertex. The vertex $$$1$$$ is the root. You are to answer some questions about the tree.
A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a node $$$v$$$ is the next vertex on the shortest path from $$$v$$$ to the root.
Each question is defined by three integers $$$v$$$, $$$l$$$, and $$$k$$$. To get the answer to the question, you need to perform the following steps:
For example, if the sequence of integers on the path from $$$v$$$ to the root is $$$[2, 2, 1, 7, 1, 1, 4, 4, 4, 4]$$$, $$$l = 2$$$ and $$$k = 2$$$, then the answer is $$$1$$$.
Please answer all questions about the tree.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^6$$$). Description of the test cases follows.
The first line of each test case contains two integers $$$n$$$, $$$q$$$ ($$$1 \leq n, q \leq 10^6$$$) — the number of vertices in the tree and the number of questions.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$), where $$$a_i$$$ is the number written on the $$$i$$$-th vertex.
The third line contains $$$n-1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$), where $$$p_i$$$ is the parent of node $$$i$$$. It's guaranteed that the values $$$p$$$ define a correct tree.
Each of the next $$$q$$$ lines contains three integers $$$v$$$, $$$l$$$, $$$k$$$ ($$$1 \leq v, l, k \leq n$$$) — descriptions of questions.
It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$10^6$$$.
For each question of each test case print the answer to the question. In case of multiple answers, print any.
2 3 3 1 1 1 1 2 3 1 1 3 1 2 3 2 1 5 5 1 2 1 1 2 1 1 2 2 3 1 1 2 1 2 4 1 1 4 2 1 4 2 2
1 -1 1 1 1 2 1 -1
Name |
---|