{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYen-Jen loves loli very much!!!\u003c/p\u003e\n\u003cp\u003eNow, he is solving a problem with a cute, cat-eared loli. But he drinks too much yesterday and his mind is not open yet, so he asked you to solve the following problem for him!\u003c/p\u003e\n\u003cp\u003eGiven a rooted tree with $N$ vertices(vertices are numbered from $1$ to $N$) whose root is $1$. In every node, there\u0027s an uppercase letter on it.\u003c/p\u003e\n\u003cp\u003eDefine one way to generate a string with length $L$ as follows:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003eselect a start node $X$\u003c/li\u003e\n \u003cli\u003ego to the parent node $L - 1$ times\u003c/li\u003e\n \u003cli\u003ewhenever goes to a node, append the corresponding English letter to the end of the string\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eNow 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$.\u003c/p\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eThe first line of the input contains two integer $N, Q$ which is mentioned above.\u003c/p\u003e\n\u003cp\u003eIn the next line, a string $S$ is given, the $i^{th}$ character means the English letter on the $i^{th}$ node.\u003c/p\u003e\n\u003cp\u003eThen, there are $N - 1$ integers in one line, the $i^{th}$ integer is the parent of node $i + 1$.\u003c/p\u003e\n\u003cp\u003eThen, 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.\u003c/p\u003e\n\u003cp\u003eIt is guaranteed that the testcase is valid!\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003e$1 \\leq N, Q \\leq 3 \\times 10 ^ 5$\u003c/li\u003e\n \u003cli\u003e$1 \\leq X_i, L_i \\leq N$\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eOutput $Q$ lines, the $i^{th}$ represents the ansewr of the $i^{th}$ query.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 3\nABABBA\n1 1 3 3 4\n2 2\n2 1\n6 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3\n1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}