#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 正在和一位可爱的猫娘一起解决一个问题。但他昨天喝得太多了,头脑还没清醒,所以他请你帮他解决以下问题!
给定一棵有 个顶点的有根树(顶点编号从 到 ),其根为 。每个节点上都有一个大写字母。
定义一种生成长度为 的字符串的方法如下:
- 选择一个起始节点
- 向上访问父节点 次
- 每次到达一个节点,就将该节点对应的大写字母追加到字符串的末尾
现在有 个询问,在第 个询问中,给定一个起始节点 。请统计有多少个起始节点 (包括 自身),使得从 出发可以生成与从 出发完全相同的字符串。
输入格式
第一行包含两个整数 ,含义如上所述。
接下来一行,给出一个字符串 ,其第 个字符表示第 个节点上的大写字母。
再接下来一行,包含 个整数,第 个整数表示节点 的父节点编号。
接下来 行,每行对应一个询问。在每行中,给出两个整数 ,含义如题目描述所述。
保证所有测试数据均为合法!
输出格式
输出 行,第 行表示第 个询问的答案。
6 3
ABABBA
1 1 3 3 4
2 2
2 1
6 4
3
3
1
提示
翻译由 DeepSeek V4 Pro 完成