#P18450. Suffix Structure

Suffix Structure

Suffix Structure

题目描述

对于字符串 u=u1u2⋯uku=u_1u_2\cdots u_k,用 pre⁡(u,i)\operatorname{pre}(u,i) 表示由前 ii 个字符组成的前缀 u1⋯uiu_1\cdots u_i;特别地,pre⁡(u,0)\operatorname{pre}(u,0) 为空串。对于两个字符串 u,vu,v,用 u+vu+v 表示先写 uu、再写 vv 得到的连接串。

给定长度为 mm 的字符串 t=t1t2⋯tmt=t_1t_2\cdots t_m,以及一棵有 n+1n+1 个顶点、以顶点 00 为根的树。顶点编号为 0,1,…,n0,1,\ldots,n,每条边带有一个字符。本题的字符集可能超过 26 个字符,字符使用正整数编号。

令 sis_i 为从根到顶点 ii 的路径上各边的字符依次连接成的字符串,d(i)d(i) 为这条路径的边数。定义

$$f(i,j)=\max\{d(x)\mid s_x\text{ 是 }s_i+\operatorname{pre}(t,j)\text{ 的后缀}\}.$$

这里 xx 可以为 00;s0s_0 是空串,而空串是任何字符串的后缀。

对于每个 j=1,2,…,mj=1,2,\ldots,m,计算

gj=∑i=1nf(i,j).g_j=\sum_{i=1}^{n}f(i,j).

注意求和的初始顶点为 11 到 nn,不包含顶点 00。

输入格式

输入包含多组测试数据。第一行是整数 TT,表示测试数据组数。每组数据包含四行:

  • 第一行包含两个整数 n,mn,m,满足 1≤n,m≤2×1051\le n,m\le2\times10^5。
  • 第二行包含 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n,其中 0≤pi<i0\le p_i<i,表示顶点 ii 的父亲为 pip_i。
  • 第三行包含 nn 个整数 c1,c2,…,cnc_1,c_2,\ldots,c_n,其中 1≤ci≤n1\le c_i\le n,表示从 pip_i 到 ii 的边上的字符编号为 cic_i。保证对于所有 i≠ji\ne j,都有 pi≠pjp_i\ne p_j 或 ci≠cjc_i\ne c_j,即同一个父亲的各条子边上的字符互不相同。
  • 第四行包含 mm 个整数 t1,t2,…,tmt_1,t_2,\ldots,t_m,其中 1≤ti≤n1\le t_i\le n,表示字符串 tt 的字符。

保证所有测试数据的 nn 之和不超过 2×1052\times10^5,所有测试数据的 mm 之和也不超过 2×1052\times10^5。这两个总和限制分别成立。

输出格式

对于每组数据,输出一行 mm 个整数 g1,g2,…,gmg_1,g_2,\ldots,g_m,相邻整数用一个空格分隔。

请勿在每一行末尾输出额外的空格,否则你的程序可能被判为错误。

原样例

2
11 3
0 1 2 0 4 5 4 6 0 9 10
1 3 2 2 1 3 4 1 3 2 1
3 2 4
5 16
0 0 0 1 4
1 2 3 2 2
2 1 3 3 2 1 3 2 1 3 2 2 1 1 2 1
17 26 22
8 5 5 5 5 5 5 5 5 5 5 5 5 5 10 5

原样例说明

考虑第一组样例的 f(11,1)f(11,1) 和 f(11,2)f(11,2)。有 s11={3,2,1}s_{11}=\{3,2,1\},因此

s11+pre⁡(t,1)={3,2,1,3}.s_{11}+\operatorname{pre}(t,1)=\{3,2,1,3\}.

树中表示的最长后缀是 s6={2,1,3}s_6=\{2,1,3\},所以 f(11,1)=d(6)=3f(11,1)=d(6)=3。

类似地,

s11+pre⁡(t,2)={3,2,1,3,2}.s_{11}+\operatorname{pre}(t,2)=\{3,2,1,3,2\}.

此时树中表示的最长后缀为 s3={1,3,2}s_3=\{1,3,2\},所以 f(11,2)=d(3)=3f(11,2)=d(3)=3。