2764: T3 徐老师的春秋大梦
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：0
题目描述
> 【睿爸信奥】的学生都被其他老师拐走了，徐老师没课上，他觉得很无聊，于是趴在课桌上深深睡去。
徐老师梦见来很多很多优秀的学生，形成了一棵大小为 $n$ 的有根树，根节点为 $1$ 号点，且根节点的深度为 $1$ 。
树上每个结点代表徐老师的一个学生，每个结点有一个名字 $s_i$，用小写字母 $a\sim z$ 表示表示。
徐老师对他的学生很满意，于是他开始了 $m$ 次点名，每次点名会把结点 $u$ 的子树中，深度为 $k$ 的结点的名字都取出来，然后进行**重排**。
现在徐老师想知道，重排后能否形成一个回文串？
回文串定义为一个字符串从左往右读，和从右往左读是一样的，比如`aabbcbbaa`、`abba` 等。
徐老师梦见来很多很多优秀的学生，形成了一棵大小为 $n$ 的有根树，根节点为 $1$ 号点，且根节点的深度为 $1$ 。
树上每个结点代表徐老师的一个学生，每个结点有一个名字 $s_i$，用小写字母 $a\sim z$ 表示表示。
徐老师对他的学生很满意，于是他开始了 $m$ 次点名，每次点名会把结点 $u$ 的子树中，深度为 $k$ 的结点的名字都取出来，然后进行**重排**。
现在徐老师想知道，重排后能否形成一个回文串？
回文串定义为一个字符串从左往右读，和从右往左读是一样的，比如`aabbcbbaa`、`abba` 等。
输入
第一行两个数 $n,m$，表示树上结点个数和徐老师点名的次数。
第二行 $n-1$ 个数，第 $i$ 个数表示树上第 $i+1$ 的节点的父亲结点的编号 $p_i$，保证父亲结点的编号比该结点小。
第三行是一个长度为 $n$ 的字符串 $s$，其中 $s_i$ 表示 $i$ 号结点的名字
接下来 $m$ 行，每行一个询问 $u,k$，表示查询的是 $u$ 子树中深度为 $k$ 的结点。
第二行 $n-1$ 个数，第 $i$ 个数表示树上第 $i+1$ 的节点的父亲结点的编号 $p_i$，保证父亲结点的编号比该结点小。
第三行是一个长度为 $n$ 的字符串 $s$，其中 $s_i$ 表示 $i$ 号结点的名字
接下来 $m$ 行，每行一个询问 $u,k$，表示查询的是 $u$ 子树中深度为 $k$ 的结点。
输出
$m$ 行，如果能构成回文串，输出`huiwen`，否则输出`?`。
样例输入 复制
8 7
1 1 2 2 5 5 3
dacxyppx
1 1
1 2
1 3
1 4
2 2
2 3
3 3样例输出 复制
huiwen
?
huiwen
huiwen
huiwen
?
huiwen提示
## 样例解释：
询问 $1$ ，`a` 是回文；
询问 $2$ ，`ac` 重排不出回文串；
询问 $3$ ，`xyx` 是回文；
询问 $4$ ，`pp`是回文；
询问 $5$ ，`a` 是回文；
询问 $6$ ，`xy` 重排不出回文串；
询问 $7$ ，`x` 是回文。
## 数据范围
对于全部数据 $1\le n,m\le10^4$，$1\le r_i\le n-1$，$1\le x\le n$。
| 测试点 | $n，m $ | 特殊性质 |
| :-------------------: | :----------------------------------------------------------: | :----------------------------------------: |
| 对于前 $20 \%$ 的数据 | $n\leq 10$， $m\le 20$。 | 无 |
| 对于前 $40 \%$ 的数据 | $n,m \leq 1000$ | 无 |
| 对于$100\%$的数据 | $1\le n,m\leq 10^4$， $1 \le p_i<i$， $s_i$ 为小写英文字母， $1\le u ,k\le n$ | 保证 $u$ 子树内至少有一个深度为 $k$ 的结点 |
询问 $1$ ，`a` 是回文；
询问 $2$ ，`ac` 重排不出回文串；
询问 $3$ ，`xyx` 是回文；
询问 $4$ ，`pp`是回文；
询问 $5$ ，`a` 是回文；
询问 $6$ ，`xy` 重排不出回文串；
询问 $7$ ，`x` 是回文。
## 数据范围
对于全部数据 $1\le n,m\le10^4$，$1\le r_i\le n-1$，$1\le x\le n$。
| 测试点 | $n，m $ | 特殊性质 |
| :-------------------: | :----------------------------------------------------------: | :----------------------------------------: |
| 对于前 $20 \%$ 的数据 | $n\leq 10$， $m\le 20$。 | 无 |
| 对于前 $40 \%$ 的数据 | $n,m \leq 1000$ | 无 |
| 对于$100\%$的数据 | $1\le n,m\leq 10^4$， $1 \le p_i<i$， $s_i$ 为小写英文字母， $1\le u ,k\le n$ | 保证 $u$ 子树内至少有一个深度为 $k$ 的结点 |