P13960 [ICPC 2023 Nanjing R] 后缀结构

给定字符串 $u = u_1 \dots u_n$，令 $\mathrm{pre}(u, i)$ 表示前缀 $u_1 \dots u_i$。特别地，$\mathrm{pre}(u, 0)$ 是空字符串。 对于两个字符串 $u = u_1 \dots u_n$ 与 $v = v_1 \dots v_m$，令 $u+v$ 表示连接后的字符串 $u_1 \dots u_n v_1 \dots v_m$。 给定长度为 $m$ 的字符串 $t=t_1 \dots t_m$ 和一棵有 $(n + 1)$ 个节点的树 $T$，节点编号为 $0, 1, \dots, n$，其中节点 $0$ 是根。每条边上都有一个字符。请注意，在本题中，字母表中可能会有多于 $26$ 个字符。 考虑如下函数 $$f(i,j) = \max\{d(x) \mid s_x\text{ 是 }s_i+ \mathrm{pre}(t,j)\text{ 的后缀}\}$$ 其中 $s_i$ 是从根到节点 $i$ 的最短路径上所有字符连接而成的字符串，$d(i)$ 是从根到节点 $i$ 的最短路径经过的边数。 您需要计算 $g_1, g_2, \dots, g_m$，其中 $g_j=\sum\limits_{i=1}^{n} f(i,j)$。 请注意，$s_0$ 是空字符串，空字符串是任何字符串的后缀。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据： 第一行输入两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \times 10^5$）。 第二行输入 $n$ 个整数 $p_1, p_2, \dots, p_n$（$0 \le p_i < i$），其中 $p_i$ 表示节点 $i$ 的父节点。 第三行输入 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le n$），其中 $c_i$ 表示从节点 $p_i$ 到节点 $i$ 的边上的字符是字母表中第 $c_i$ 个字符。保证对于所有 $i \ne j$，有 $p_i \ne p_j$ 或 $c_i \ne c_j$。 第四行输入 $m$ 个整数 $t_1, t_2, \dots, t_m$（$1 \le t_i \le n$），其中 $t_i$ 是字符串 $t$ 中的第 $i$ 个字符。 保证所有数据 $n$ 之和与 $m$ 之和均不超过 $2 \times 10^5$。

每组数据输出一行 $m$ 个由单个空格分隔的整数 $g_1, g_2, \dots, g_m$。 请不要在行末输出多余空格，否则您的答案可能会被认为是错误的！

我们来计算第一组样例数据中的 $f(11, 1)$ 和 $f(11, 2)$ 以便您更好地理解。有 $s_{11} = \{3, 2, 1\}$，所以 $s_{11} + \text{pre}(t, 1) = \{3, 2, 1, 3\}$。因为 $s_6 = \{2, 1, 3\}$ 是该字符串存在于树中的最长后缀，所以 $f(11, 1) = d(6) = 3$。另外 $s_{11} + \text{pre}(t, 2) = \{3, 2, 1, 3, 2\}$，那么 $s_3 = \{1, 3, 2\}$ 是该字符串存在于树中的最长后缀，所以 $f(11, 2) = d(3) = 3$。