CF1591E Frequency Queries

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

对于每个测试用例的每个问题，输出该问题的答案。如果有多个答案，输出任意一个。

由 ChatGPT 4.1 翻译