Frequency Queries
Contest: Technocup 2022 - Elimination Round 3
Difficulty rating: 2400
Tags: data structures, dfs and similar, trees

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 format:
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 format:
For each question of each test case print the answer to the question. In case of multiple answers, print any.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
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

Example output:
1 -1 1 
1 1 2 1 -1

Editorial:
Let's traverse through the tree with depth-first-search from the root and maintain counting array ($$$cnt_x$$$ := "number of occasions of x in the sequence"). When dfs enters vertex $$$v$$$, it increases $$$cnt_{a_v}$$$ by $$$1$$$, then it proceeds all queries correspondent to $$$v$$$. When dfs leaves the vertex, it decreases $$$cnt_{a_v}$$$ by $$$1$$$.
Let's maintain this quantities:
• Sorting permuation $$$p$$$ of $$$cnt$$$, initially — $$$1, 2, \ldots, n$$$.
• Inverse permuation $$$p^{-1}$$$.
• For each $$$x \in \{0, 1, \ldots, n\}$$$, "lower_bound" $$$lb_x$$$ in sorted array. More formally, minimal $$$i$$$ such that $$$cnt_{p_i} \geq x$$$.
When we want to increase $$$cnt_x$$$ by $$$1$$$:
• Move $$$x$$$ in the end of block of same values in sorted array. So we need to swap ($$$p^{-1}_i$$$)-th and $$$(lb_{cnt_x+1}-1$$$)-th positions of $$$p$$$.
• Change $$$p^{-1}$$$ accrodingly to the change of $$$p$$$.
• Decrease $$$lb_{cnt_x + 1}$$$ by $$$1$$$. Note: that's the only $$$lb$$$ value that after during this operation.
• Increase $$$cnt_x$$$.
Operation of decreasing $$$cnt_x$$$ by $$$1$$$ can be done symmetrically.
Note: if answer exists, then one of possible answers is $$$p_{lb_l + k - 1}$$$.
Total complexity: $$$\mathcal{O}(n + q)$$$.