#P15604. [2025年山东第一轮集训]字符串大师

[2025年山东第一轮集训]字符串大师

题目描述

给定一棵有 ll 个节点的 trie 树。

对于树上的某个点 ii,定义 uiu_i 为从根节点到 ii 的路径上的字符从浅到深顺次连接得到的字符串,其中:

u1=∅u_1=\varnothing

给出若干字符串:

s1,s2,…,sns_1,s_2,\ldots,s_n

和一个序列:

a1,a2,…,ama_1,a_2,\ldots,a_m

令:

T=sa1+sa2+⋯+samT=s_{a_1}+s_{a_2}+\cdots+s_{a_m}

其中 ++ 表示字符串拼接。

对于每一个 ui (1<i≤l)u_i\ (1<i\le l),求 uiu_i 在 TT 中出现的次数 ansians_i。

输入格式

输入第一行包含四个正整数:

l, n, m, wl,\ n,\ m,\ w

接下来一行包含 l−1l-1 个正整数,分别表示:

c2,c3,…,clc_2,c_3,\ldots,c_l

即 trie 树上每个点到父亲的边上的字符。

接下来一行包含 l−1l-1 个正整数,分别表示:

fa2,fa3,…,falfa_2,fa_3,\ldots,fa_l

即 trie 树上每个点的父亲。

接下来 nn 行,每行首先有一个正整数表示 ∣si∣|s_i|,然后 ∣si∣|s_i| 个正整数给出 sis_i。

接下来一行包含 mm 个正整数,分别表示:

a1,a2,…,ama_1,a_2,\ldots,a_m

输出格式

输出一行 l−1l-1 个非负整数,分别表示:

ans2,ans3,…,anslans_2,ans_3,\ldots,ans_l

样例输入 #1

7 3 6 2
1 2 2 1 1 1
1 1 2 2 3 4
3 1 1 1
4 1 2 1 2
3 2 2 1
1 3 2 3 1 1

样例输出 #1

13 6 3 9 3 1

数据范围

记:

S=∑i=1n∣si∣S=\sum_{i=1}^{n}|s_i|

对于所有数据,保证:

1≤l≤1051\le l\le 10^5 1≤n≤1001\le n\le 100 1≤m≤1061\le m\le 10^6 1≤S≤3×1061\le S\le 3\times 10^6 1≤fai≤l1\le fa_i\le l 1≤w≤4×1061\le w\le 4\times 10^6

所有输入的字符均属于 [1,w][1,w]。

保证输入的 fafa 构成一棵以 11 为根的树。

子任务

子任务编号 l≤l\le m≤m\le S≤S\le w≤w\le trie 树形态 分值
1 20002000 4×1064\times 10^6 - 15
2 10510^5 10610^6 3×1063\times 10^6 fai=i−1 (1<i≤n)fa_i=i-1\ (1<i\le n) 20
3 20002000 2626 - 25
4 10510^5 5×1055\times 10^5 20
5 3×1063\times 10^6 4×1064\times 10^6