33OJ
登录 注册

#P17742. [ICPC 2019 Xuzhou R] Loli, Yen-Jen, and a cool problem

[ICPC 2019 Xuzhou R] Loli, Yen-Jen, and a cool problem

背景

删除了原题中不和谐的内容。

题目描述

现在,Yen-Jen 正在和一位可爱的猫娘一起解决一个问题。但他昨天喝得太多了,头脑还没清醒,所以他请你帮他解决以下问题!

给定一棵有 NN 个顶点的有根树(顶点编号从 11 到 NN),其根为 11。每个节点上都有一个大写字母。

定义一种生成长度为 LL 的字符串的方法如下:

  • 选择一个起始节点 XX
  • 向上 访问父节点 L−1L - 1 次
  • 每次到达一个节点,就将该节点对应的大写字母追加到字符串的末尾

现在有 QQ 个询问,在第 ii 个询问中,给定一个起始节点 XiX_i。请统计有多少个起始节点 YY(包括 XiX_i 自身),使得从 YY 出发可以生成与从 XiX_i 出发完全相同的字符串。

输入格式

第一行包含两个整数 N,QN, Q,含义如上所述。

接下来一行,给出一个字符串 SS,其第 ii 个字符表示第 ii 个节点上的大写字母。

再接下来一行,包含 N−1N - 1 个整数,第 ii 个整数表示节点 i+1i + 1 的父节点编号。

接下来 QQ 行,每行对应一个询问。在每行中,给出两个整数 Xi,LiX_i, L_i,含义如题目描述所述。

保证所有测试数据均为合法!

  • 1≤N,Q≤3×1051 \leq N, Q \leq 3 \times 10 ^ 5
  • 1≤Xi,Li≤N1 \leq X_i, L_i \leq N

输出格式

输出 QQ 行,第 ii 行表示第 ii 个询问的答案。

6 3
ABABBA
1 1 3 3 4
2 2
2 1
6 4
3
3
1

提示

翻译由 DeepSeek V4 Pro 完成