CF570D.Tree Requests

Roman planted a tree consisting of n vertices. Each vertex contains a lowercase English letter. Vertex 1 is the root of the tree, each of the n - 1 remaining vertices has a parent in the tree. Vertex is connected with its parent by an edge. The parent of vertex i is vertex p__i, the parent index is always less than the index of the vertex (i.e., p__i < i).

The depth of the vertex is the number of nodes on the path from the root to v along the edges. In particular, the depth of the root is equal to 1.

We say that vertex u is in the subtree of vertex v, if we can get from u to v, moving from the vertex to the parent. In particular, vertex v is in its subtree.

Roma gives you m queries, the i-th of which consists of two numbers v__i, h__i. Let's consider the vertices in the subtree v__i located at depth h__i. Determine whether you can use the letters written at these vertices to make a string that is a palindrome. The letters that are written in the vertexes, can be rearranged in any order to make a palindrome, but all letters should be used.

罗马种了一棵包含 $n$ 个顶点的树。每个顶点上写有一个小写英文字母。顶点 $1$ 是这棵树的根，其余 $n-1$ 个顶点在树中均有父节点。每个顶点通过一条边与其父节点相连。顶点 $i$ 的父节点是顶点 $p_i$，且父节点的编号恒小于该顶点的编号（即 $p_i < i$）。

一个顶点的深度定义为从根节点到该顶点 $v$ 沿边所经过的节点数（含端点）。特别地，根节点的深度为 $1$。

若从顶点 $u$ 出发，不断沿父边向上移动可到达顶点 $v$，则称顶点 $u$ 位于顶点 $v$ 的子树中。特别地，顶点 $v$ 自身也属于其自身的子树。

罗玛向你提出 $m$ 个查询，其中第 $i$ 个查询包含两个整数 $v_i$ 和 $h_i$。考虑顶点 $v_i$ 的子树中所有深度恰好为 $h_i$ 的顶点。请判断：能否将这些顶点上的字母重新排列（可任意调整顺序），构成一个回文串？注意：必须使用这些顶点上的全部字母。

The first line contains two integers n, m (1 ≤ n, m ≤ 500 000) — the number of nodes in the tree and queries, respectively.

The following line contains n - 1 integers _p_2, _p_3, ..., p__n — the parents of vertices from the second to the n-th (1 ≤ p__i < i).

The next line contains n lowercase English letters, the i-th of these letters is written on vertex i.

Next m lines describe the queries, the i-th line contains two numbers v__i, h__i (1 ≤ v__i, h__i ≤ n) — the vertex and the depth that appear in the i-th query.

第一行包含两个整数 $n$、$m$（$1 \leq n, m \leq 500\,000$），分别表示树中节点的数量和查询的数量。

接下来一行包含 $n-1$ 个整数 $p_2,\,p_3,\,\dots,\,p_n$，表示从第 $2$ 号节点到第 $n$ 号节点的父节点（$1 \leq p_i < i$）。

下一行包含 $n$ 个小写英文字母，其中第 $i$ 个字母写在第 $i$ 号节点上。

接下来的 $m$ 行描述查询，其中第 $i$ 行包含两个数 $v_i$、$h_i$（$1 \leq v_i,\,h_i \leq n$），分别表示第 $i$ 个查询中指定的节点和深度。

Print m lines. In the i-th line print "Yes" (without the quotes), if in the i-th query you can make a palindrome from the letters written on the vertices, otherwise print "No" (without the quotes).

输出 m 行。在第 i 行中，如果在第 i 次查询中能够利用顶点上的字母构成回文串，则输出 "Yes"（不带引号）；否则输出 "No"（不带引号）。

String s is a palindrome if reads the same from left to right and from right to left. In particular, an empty string is a palindrome.

Clarification for the sample test.

In the first query there exists only a vertex 1 satisfying all the conditions, we can form a palindrome "z".

In the second query vertices 5 and 6 satisfy condititions, they contain letters "с" and "d" respectively. It is impossible to form a palindrome of them.

In the third query there exist no vertices at depth 1 and in subtree of 4. We may form an empty palindrome.

In the fourth query there exist no vertices in subtree of 6 at depth 1. We may form an empty palindrome.

In the fifth query there vertices 2, 3 and 4 satisfying all conditions above, they contain letters "a", "c" and "c". We may form a palindrome "cac".

字符串 $s$ 是回文串，当且仅当它从左到右读与从右到左读完全相同。特别地，空字符串是回文串。

样例测试的说明：

在第一个查询中，仅存在顶点 1 满足所有条件，我们可以用其构成回文串 "z"。

在第二个查询中，顶点 5 和 6 满足条件，它们分别包含字母 "с" 和 "d"。无法用它们构成回文串。

在第三个查询中，在深度为 1 且位于顶点 4 的子树内的顶点不存在。此时可构成空回文串。

在第四个查询中，在深度为 1 且位于顶点 6 的子树内的顶点不存在。此时可构成空回文串。

在第五个查询中，顶点 2、3 和 4 满足上述所有条件，它们分别包含字母 "a"、"c" 和 "c"。我们可以用它们构成回文串 "cac"。