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

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 $N$ vertices (vertices are numbered from $1$ to $N$) whose root is $1$. In every node, there's an uppercase letter on it. Define one way to generate a string with length $L$ as follows: - select a start node $X$ - go to the parent node $L - 1$ times - whenever goes to a node, append the corresponding English letter to the end of the string Now there are $Q$ queries, in the $i^{th}$ query, a start node $X_i$ is given. Please count the number of starting node $Y$ (include $X_i$), such that $Y$ can generate the same string as $X_i$.

The first line of the input contains two integer $N, Q$ which is mentioned above. In the next line, a string $S$ is given, the $i^{th}$ character means the English letter on the $i^{th}$ node. Then, there are $N - 1$ integers in one line, the $i^{th}$ integer is the parent of node $i + 1$. Then, there are $Q$ lines, the $i^{th}$ line represents the $i^{th}$ query. In each line, $X_i, L_i$ is given, which is mentioned in the description. It is guaranteed that the testcase is valid! - $1 \leq N, Q \leq 3 \times 10 ^ 5$ - $1 \leq X_i, L_i \leq N$

Output $Q$ lines, the $i^{th}$ represents the answer of the $i^{th}$ query.