← 返回题目列表

Codeforces · 1585/E

E. 频率查询

中文机器翻译题面 查看原题

Petya 有一个有根树,每个顶点上都写有一个整数。顶点 $$$1$$$ 是根。你要回答一些关于这棵树的问题。

树是没有循环的连通图。有根树有一个特殊的顶点,称为根。节点 $$$v$$$ 的父节点是从 $$$v$$$ 到根的最短路径上的下一个顶点。

每个问题由三个整数 $$$v$$$、$$$l$$$ 和 $$$k$$$ 定义。要获得问题的答案,您需要执行以下步骤:

- 首先,记下从顶点$$$v$$$到根的最短路径上写入的所有整数的序列(包括$$$v$$$和根中写入的整数)。
- 计算每个整数出现的次数。删除出现次数少于 $$$l$$$ 的所有整数。
- 替换序列,删除所有重复项并按原始列表中出现的次数按升序对元素进行排序。如果出现平局,您可以任意选择这些元素的顺序。
- 问题的答案是剩余序列中的第 $$$k$$$ 个数字。请注意,答案并不总是唯一确定的,因为可能有多个顺序。此外,此步骤的序列长度可能小于 $$$k$$$,在这种情况下答案是 $$$-1$$$。

例如,如果从 $$$v$$$ 到根的路径上的整数序列为 $$$[2, 2, 1, 7, 1, 1, 4, 4, 4, 4]$$$、$$$l = 2$$$ 和 $$$k = 2$$$,则答案为 $$$1$$$。

请回答有关树的所有问题。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^6$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \leq n, q \leq 10^6$$$) — 树中的顶点数和问题数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$),其中 $$$a_i$$$ 是写在第 $$$i$$$ 个顶点上的数字。

第三行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$),其中 $$$p_i$$$ 是节点 $$$i$$$ 的父节点。保证值 $$$p$$$ 定义正确的树。

接下来的 $$$q$$$ 行包含三个整数 $$$v$$$, $$$l$$$, $$$k$$$ ($$$1 \leq v, l, k \leq n$$$) — 问题的描述。

保证所有测试用例的 $$$n$$$ 总和和 $$$q$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例的每个问题,打印问题的答案。如果有多个答案,请打印其中一个。

示例

输入 #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