P9997 [Ynoi2000] pmpkmp

Given a tree, each edge of the tree has a character on it. A constant $X$ is given. There are two types of operations. Each operation inputs three integers and a string: `1 x y S`: For the edges on the directed simple path from $x$ to $y$, replace the character on the $i$-th edge of the path with the corresponding character $S_i$ in $S$. It is guaranteed that the number of edges on the path from $x$ to $y$ is $X$. `2 x y S`: Query the number of matches of $S$ on the string formed by the directed simple path from $x$ to $y$ (here, matching means: treat $S$ as the pattern string and match it against the path string position by position). For example, if $S = 121$ and the path string is $1212122$, then it matches 2 times, at positions $[1,3]$ and $[3,5]$. For all strings $S$ above, indices start from $1$. It is guaranteed that the length of every input string is $X$.

The first line contains three integers $n, m, X$ separated by spaces. The next line contains $n - 1$ integers. The $i$-th integer denotes the parent $f_{i+1}$ of node $i+1$. It is guaranteed that the parent index of each node is smaller than the node index. The next line contains $n - 1$ characters. The $i$-th character denotes the character $a_{i+1}$ on the edge from node $i+1$ to its parent. Then follow $m$ lines. Each line contains three integers $opt, x, y$ separated by spaces and a string $S$ of length $X$, representing one operation.

Output a total of $m$ lines. Each line contains one integer, representing the answer to each operation of type $2$.

Idea: nzhtl1477, Solution: ComeIntoPower&nzhtl1477&ccz181078, Code: ccz181078, Data: ccz181078. Constraints: For $10\%$ of the testdata, $1 \le n, m \le 250$. For another $10\%$ of the testdata, there are no type $1$ operations. For another $10\%$ of the testdata, $X = 1$. For another $10\%$ of the testdata, $X \le 3$. For another $10\%$ of the testdata, $X \ge 20000$. For another $10\%$ of the testdata, $f_i = i - 1$. For another $10\%$ of the testdata, $a_i \le 1$. For another $10\%$ of the testdata, $1 \le n, m \le 2.5 \times 10^4$, and $mX \le 2.5 \times 10^4$. For another $10\%$ of the testdata, $1 \le n, m \le 2.5 \times 10^5$, and $mX \le 2.5 \times 10^5$. For $100\%$ of the testdata, $1 \le n, m, X \le 5 \times 10^5$. The alphabet consists of integers in $[1,9]$, and $mX \le 5 \times 10^5$. Translated by ChatGPT 5