CF570D Tree Requests

Roman 种了一棵有 $n$ 个节点的树。每个节点上都写有一个小写英文字母。节点 $1$ 是这棵树的根，每个剩余的 $n-1$ 个节点都有一个父节点。每个节点与其父节点之间通过一条边相连。第 $i$ 个节点的父节点是 $p_i$，且父节点的编号一定小于自身编号（即 $p_i < i$）。 节点的深度定义为从根到 $v$ 的路径上经过的节点数。特别地，根节点的深度为 $1$。 如果可以从节点 $u$ 沿着父节点指针移动到节点 $v$，则称节点 $u$ 在节点 $v$ 的子树中。特别地，节点 $v$ 也在它自己的子树中。 Roman 给你 $m$ 次询问，第 $i$ 次询问包含两个整数 $v_i$、$h_i$。请考虑节点 $v_i$ 的子树中，深度为 $h_i$ 的所有节点。请判断能否用这些节点上写的所有字母重新排列，组成一个回文串。可以任意排列这些字母，且所有字母都必须被使用。

第一行包含两个整数 $n$、$m$（$1 \leq n, m \leq 500000$），分别表示树的节点数和询问数量。 第二行为 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$，表示第 $2$ 到第 $n$ 个节点的父节点编号（$1 \leq p_i < i$）。 第三行包含 $n$ 个小写英文字母，第 $i$ 个字母代表第 $i$ 个节点上的字母。 接下来 $m$ 行，每行两个整数 $v_i$、$h_i$（$1 \leq v_i, h_i \leq n$），表示一次询问：指定的节点及深度。

输出 $m$ 行，每行一个答案。如果对于第 $i$ 次询问，可以用这些节点的字母组成回文串，则输出 “Yes”，否则输出 “No”。

如果一个字符串从左往右读和从右往左读是一样的，则为回文串。特别地，空串也是回文串。 样例解释： 对于第一个询问，只有节点 $1$ 满足条件，可以组成回文串 “z”。 对于第二个询问，节点 $5$ 和 $6$ 满足条件，字母分别为 “c” 和 “d”，无法组成回文串。 对于第三个询问，在节点 $4$ 的子树中没有深度为 $1$ 的节点，可以组成空回文串。 对于第四个询问，在节点 $6$ 的子树中没有深度为 $1$ 的节点，可以组成空回文串。 对于第五个询问，节点 $2$、$3$ 和 $4$ 满足条件，它们的字母分别为 “a”、“c”、“c”，可以组成回文串 “cac”。 由 ChatGPT 5 翻译