P13960 [ICPC 2023 Nanjing R] Suffix Structure

For a string $u = u_1 \dots u_n$, let $\mathrm{pre}(u, i)$ be the prefix $u_1 \dots u_i$. In particular, $\mathrm{pre}(u, 0)$ is empty string. For two strings $u = u_1 \dots u_n$ and $v = v_1 \dots v_m$, let $u+v$ be the concatenation $u_1 \dots u_n v_1 \dots v_m$. You are given a string $t=t_1 \dots t_m$ of length $m$ and a tree $T$ with $(n + 1)$ vertices labeled with $0, 1, \dots, n$ rooted at vertex $0$. Each edge is associated with a character. Please note that in this problem, the alphabet may contain more than $26$ characters. Consider the following function $$f(i,j) = \max\{d(x) \mid s_x\text{ is a suffix of }s_i+ \mathrm{pre}(t,j)\}$$ where $s_i$ be the concatenation of characters on the shortest path from root to vertex $i$ and $d(i)$ be the number of edges on the shortest path from the root to vertex $i$. Your task is to compute the values of $g_1, g_2, \dots, g_m$ where $g_j=\sum\limits_{i=1}^{n} f(i,j)$. Note that $s_0$ is the empty string and empty string is a suffix of any string.

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \times 10^5$). The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($0 \le p_i < i$) where $p_i$ indicates the parent of vertex $i$. The third line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$) where $c_i$ indicates that the edge from vertex $p_i$ to vertex $i$ is associated with the $c_i$-th character from the alphabet. It is guaranteed that $p_i \ne p_j$ or $c_i \ne c_j$ for all $i \ne j$. The fourth line contains $m$ integers $t_1, t_2, \dots, t_m$ ($1 \le t_i \le n$) where $t_i$ is the $i$-th character of string $t$. It is guaranteed that neither the sum of $n$ nor the sum of $m$ will exceed $2 \times 10^5$.

For each test case output one line containing $m$ integers $g_1, g_2, \dots, g_m$ separated by a space. Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

Let's calculate $f(11, 1)$ and $f(11, 2)$ in the first sample test case to help you further understand. We have $s_{11} = \{3, 2, 1\}$ so $s_{11} + \text{pre}(t, 1) = \{3, 2, 1, 3\}$. As $s_6 = \{2, 1, 3\}$ is its longest suffix existing in the tree, $f(11, 1) = d(6) = 3$. Also $s_{11} + \text{pre}(t, 2) = \{3, 2, 1, 3, 2\}$ and $s_3 = \{1, 3, 2\}$ is its longest suffix existing in the tree, so $f(11, 2) = d(3) = 3$.