CF570D Tree Requests

题目描述

Roman 有一棵以 $1$ 号顶点为根的有根树，树中共有 $n$ 个顶点。每个顶点上写有一个小写英文字母。根节点的深度为 $1$，如果一个点的父亲深度为 $d$，则它的深度为 $d+1$。

如果从某个顶点 $u$ 沿父亲指针不断向上可以到达顶点 $v$，则称 $u$ 在 $v$ 的子树中，特别地，$v$ 也在自己的子树中。

接下来有 $m$ 次询问，每次给出两个整数 $v,h$。请取出以 $v$ 为根的子树中，所有深度恰好为 $h$ 的顶点上的字母。判断这些字母能否经过重新排列后组成一个回文串。所有取出的字母都必须使用；若没有取出任何字母，也视为可以组成回文串。

输入格式

第一行两个整数 $n,m$，表示顶点数和询问数。

第二行包含 $n-1$ 个整数 $p_2,p_3,\ldots,p_n$，其中 $p_i$ 表示顶点 $i$ 的父亲。保证 $p_i<i$。

第三行一个长度为 $n$ 的小写英文字母串，第 $i$ 个字符表示顶点 $i$ 上的字母。

接下来 $m$ 行，每行两个整数 $v,h$，表示一次询问。

输出格式

对每个询问输出一行：

• 若可以重排成回文串，输出 Yes；
• 否则输出 No。

样例

样例输入

3 3
1 1
aba
1 2
1 1
2 2

样例输出

No
Yes
Yes

数据范围与约定

$1\le n,m\le 5\times 10^5$，$1\le p_i<i$，$1\le v\le n$，$1\le h\le n$。