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

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

现在，Yen-Jen 正在和一位可爱的猫娘一起解决一个问题。但他昨天喝得太多了，头脑还没清醒，所以他请你帮他解决以下问题！ 给定一棵有 $N$ 个顶点的有根树（顶点编号从 $1$ 到 $N$），其根为 $1$。每个节点上都有一个大写字母。 定义一种生成长度为 $L$ 的字符串的方法如下： - 选择一个起始节点 $X$ - 向上$ $访问父节点 $L - 1$ 次 - 每次到达一个节点，就将该节点对应的大写字母追加到字符串的末尾 现在有 $Q$ 个询问，在第 $i$ 个询问中，给定一个起始节点 $X_i$。请统计有多少个起始节点 $Y$（包括 $X_i$ 自身），使得从 $Y$ 出发可以生成与从 $X_i$ 出发完全相同的字符串。

第一行包含两个整数 $N, Q$，含义如上所述。 接下来一行，给出一个字符串 $S$，其第 $i$ 个字符表示第 $i$ 个节点上的大写字母。 再接下来一行，包含 $N - 1$ 个整数，第 $i$ 个整数表示节点 $i + 1$ 的父节点编号。 接下来 $Q$ 行，每行对应一个询问。在每行中，给出两个整数 $X_i, L_i$，含义如题目描述所述。 保证所有测试数据均为合法！ - $1 \leq N, Q \leq 3 \times 10 ^ 5$ - $1 \leq X_i, L_i \leq N$

输出 $Q$ 行，第 $i$ 行表示第 $i$ 个询问的答案。

翻译由 DeepSeek V4 Pro 完成