Frequency Queries

4000ms

524288K

Description:

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:

First, write down the sequence of all integers written on the shortest path from the vertex $$$v$$$ to the root (including those written in the $$$v$$$ and the root).
Count the number of times each integer occurs. Remove all integers with less than $$$l$$$ occurrences.
Replace the sequence, removing all duplicates and ordering the elements by the number of occurrences in the original list in increasing order. In case of a tie, you can choose the order of these elements arbitrary.
The answer to the question is the $$$k$$$-th number in the remaining sequence. Note that the answer is not always uniquely determined, because there could be several orderings. Also, it is possible that the length of the sequence on this step is less than $$$k$$$, in this case the answer is $$$-1$$$.

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.

Input:

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$$$.

Output:

For each question of each test case print the answer to the question. In case of multiple answers, print any.

Sample Input:

Sample Output:

1 -1 1 
1 1 2 1 -1

Informação

Provedor Codeforces

Código CF1585E