Suffix Structure
题目描述
对于字符串 u=u1u2⋯uk,用 pre(u,i) 表示由前 i 个字符组成的前缀 u1⋯ui;特别地,pre(u,0) 为空串。对于两个字符串 u,v,用 u+v 表示先写 u、再写 v 得到的连接串。
给定长度为 m 的字符串 t=t1t2⋯tm,以及一棵有 n+1 个顶点、以顶点 0 为根的树。顶点编号为 0,1,…,n,每条边带有一个字符。本题的字符集可能超过 26 个字符,字符使用正整数编号。
令 si 为从根到顶点 i 的路径上各边的字符依次连接成的字符串,d(i) 为这条路径的边数。定义
$$f(i,j)=\max\{d(x)\mid s_x\text{ 是 }s_i+\operatorname{pre}(t,j)\text{ 的后缀}\}.$$
这里 x 可以为 0;s0 是空串,而空串是任何字符串的后缀。
对于每个 j=1,2,…,m,计算
gj=i=1∑nf(i,j).
注意求和的初始顶点为 1 到 n,不包含顶点 0。
输入格式
输入包含多组测试数据。第一行是整数 T,表示测试数据组数。每组数据包含四行:
- 第一行包含两个整数 n,m,满足 1≤n,m≤2×105。
- 第二行包含 n 个整数 p1,p2,…,pn,其中 0≤pi<i,表示顶点 i 的父亲为 pi。
- 第三行包含 n 个整数 c1,c2,…,cn,其中 1≤ci≤n,表示从 pi 到 i 的边上的字符编号为 ci。保证对于所有 i=j,都有 pi=pj 或 ci=cj,即同一个父亲的各条子边上的字符互不相同。
- 第四行包含 m 个整数 t1,t2,…,tm,其中 1≤ti≤n,表示字符串 t 的字符。
保证所有测试数据的 n 之和不超过 2×105,所有测试数据的 m 之和也不超过 2×105。这两个总和限制分别成立。
输出格式
对于每组数据,输出一行 m 个整数 g1,g2,…,gm,相邻整数用一个空格分隔。
请勿在每一行末尾输出额外的空格,否则你的程序可能被判为错误。
原样例
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,2)。有 s11={3,2,1},因此
s11+pre(t,1)={3,2,1,3}.
树中表示的最长后缀是 s6={2,1,3},所以 f(11,1)=d(6)=3。
类似地,
s11+pre(t,2)={3,2,1,3,2}.
此时树中表示的最长后缀为 s3={1,3,2},所以 f(11,2)=d(3)=3。