Frequency Queries

题意翻译

有一棵 $n$ 个点的有根树，每个点有一个权值 $a_i$，且给出每个点的父节点 $p_i$。 有 $q$ 个询问如 `v l k` 所示。你需要进行如下操作来得到询问的答案： 1. 写下根节点到点 $v$ 路径上的所有点权（包括根节点和 $v$ 点）。 1. 去掉其中出现次数小于 $l$ 的数。 1. 按出现次数将剩下的数升序排序。 1. 答案为去重后的第 $k$ 个数。如果不足 $k$ 个数，答案为 `-1`。 如果有出现次数相同的数，你可以将它们按任意顺序排序。 本题有多组数据，在输入的第一行以 $t$ 给出。 数据范围：$1 \leq t,n,q,\sum n,\sum q \leq 10^6,1 \leq a_i,p_i,v,l,k \leq n$。

题目描述

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.

输入输出格式

输入格式

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.

输入输出样例

输入样例 #1

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 1 2 1 -1

题意翻译

有一棵 $n$ 个点的有根树，每个点有一个权值 $a_i$，且给出每个点的父节点 $p_i$。 有 $q$ 个询问如 `v l k` 所示。你需要进行如下操作来得到询问的答案： 1. 写下根节点到点 $v$ 路径上的所有点权（包括根节点和 $v$ 点）。 1. 去掉其中出现次数小于 $l$ 的数。 1. 按出现次数将剩下的数升序排序。 1. 答案为去重后的第 $k$ 个数。如果不足 $k$ 个数，答案为 `-1`。 如果有出现次数相同的数，你可以将它们按任意顺序排序。 本题有多组数据，在输入的第一行以 $t$ 给出。 数据范围：$1 \leq t,n,q,\sum n,\sum q \leq 10^6,1 \leq a_i,p_i,v,l,k \leq n$。