← 返回题目列表

Codeforces · 570/D

D. 树请求

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

Roman 种了一棵由 n 个顶点组成的树。每个顶点都包含一个小写英文字母。顶点 1 是树的根,剩余的 n - 1 个顶点中的每一个在树中都有一个父顶点。顶点通过边与其父级连接。顶点 i 的父节点是顶点 pi,父节点索引始终小于顶点索引(即 pi < i)。

顶点的深度是沿边从根到 v 的路径上的节点数。特别地,根的深度等于1。

如果我们可以从 u 到 v,从顶点移动到父节点,我们就说顶点 u 位于顶点 v 的子树中。特别是,顶点 v 在其子树中。

Roma 给你 m 个查询,其中第 i 个由两个数字 vi、hi 组成。让我们考虑位于深度 hi 的子树 vi 中的顶点。确定是否可以使用写在这些顶点处的字母来构成回文字符串。写在顶点的字母可以以任何顺序重新排列以形成回文,但应使用所有字母。

输入

第一行包含两个整数 n, m (1 ≤ n, m ≤ 500 000) — 分别是树中的节点数和查询数。

以下行包含 n - 1 个整数 p2, p3, ..., pn — 从第二个到第 n 个顶点的父顶点 (1 ≤ pi < i)。

下一行包含n个小写英文字母,其中第i个字母写在顶点i上。

接下来 m 行描述查询,第 i 行包含两个数字 vi, hi (1 ≤ vi, hi ≤ n) — 第 i 个查询中出现的顶点和深度。

输出

打印 m 行。在第 i 行中打印“Yes”(不带引号),如果在第 i 个查询中可以根据顶点上写的字母创建回文,否则打印“No”(不带引号)。

示例

输入 #1

6 5
1 1 1 3 3
zacccd
1 1
3 3
4 1
6 1
1 2

输出 #1

Yes
No
Yes
Yes
Yes

注意

如果从左到右和从右到左读取相同,则字符串 s 是回文。特别是,空字符串是回文。

样品测试的澄清。

第一个查询中只存在满足所有条件的顶点1,我们可以形成一个回文“z”。

在第二个查询中,顶点5和6满足条件,它们分别包含字母“с”和“d”。不可能形成它们的回文。

在第三个查询中,深度 1 和 4 子树中不存在顶点。我们可以形成一个空回文。

在第四个查询中,深度为 1 的 6 子树中不存在顶点。我们可以形成一个空回文。

在第五个查询中,有满足上述所有条件的顶点 2、3 和 4,它们包含字母“a”、“c”和“c”。我们可以形成一个回文“cac”。