#P17742. [ICPC 2019 Xuzhou R] Loli, Yen-Jen, and a cool problem
[ICPC 2019 Xuzhou R] Loli, Yen-Jen, and a cool problem
Problem Description
Now, Yen-Jen is solving a problem with a cute catgirl. But he drinks too much yesterday and his mind is not open yet, so he asked you to solve the following problem for him!
Given a rooted tree with vertices (vertices are numbered from to ) whose root is . In every node, there's an uppercase letter on it.
Define one way to generate a string with length as follows:
- select a start node
- go to the parent node times
- whenever goes to a node, append the corresponding English letter to the end of the string
Now there are queries, in the query, a start node is given. Please count the number of starting node (include ), such that can generate the same string as .
Input Format
The first line of the input contains two integer which is mentioned above.
In the next line, a string is given, the character means the English letter on the node.
Then, there are integers in one line, the integer is the parent of node .
Then, there are lines, the line represents the query. In each line, is given, which is mentioned in the description.
It is guaranteed that the testcase is valid!
Output Format
Output lines, the represents the answer of the query.
6 3
ABABBA
1 1 3 3 4
2 2
2 1
6 4
3
3
1