U140400 C_树上回文

C_Class

一棵以 $1$ 为根且有 $n$ 个结点的有根树，每个结点上有写有一个小写字母，根结点深度为 $1$。 现给定 $q$ 个询问，第 $i$ 个询问包含两个正整数 $r_i， d_i$，表示询问以 $r_i$ 为根的子树中，所有深度为 $d_i$ 的结点上的字母能够构成一个回文串，若能够成回文串，输出： 输出：`Palindromic` ，反之输出：`Non Palindromic` 。

第一行：两个正整数 $n, q$。 第二行：$n-1$ 整数表示 $f_2$ 到 $f_n$，$f_i$ 表示 $i$ 号父亲的编号，保证有 1 ≤ $f_i$ ＜ $i$。 第三行：长度为 $n$ 且由小写字母组成的字符串，其中第 $i$ 个字符表示 $i$ 号结点上的字母接下去 $q$ 行，每行两个正整数 $r_i,q_i$。

输出共 $q$ 行，第 $i$ 行对应第 $i$ 个询问的答案。

#1说明 对于询问1:1为根的子树中深度为1的结点只有1号点本身，x可以认为是回文串 对于询问2:1为根的子树中深度为2的结点有2,4,5号点，h,h,a可以组成hah这个回文串 对于询问3:4为根的子树中深度为3的结点有6,7号点，y,z无法组成回文串 对于询问4:6为根的子树中深度为2的结点不存在，因此为空串，空串也可以认为是回文串 数据范围： 对于 $30\%$ 的数据， $1 \le n, q \le 20$ 对于 $50\%$ 的数据， $1 \le n,q \le 10^4$ 对于 $100\%$ 的数据 $1 \le n,q \le 5 \times 10^5$ 数据保证每个结点上的字母均为小写英语字母