【ULR #2】霸占排行榜 - 题目 - Universal Online Judge

超级管理员 Skip 蚤想把自己的 Rating 改成 $8000$。同时，他需要换一个特别长的账号名，这样在 Rating List 上它的名字就会特别显眼。

而且，如果在搜索其它跳蚤时顺便搜索到它，便能提高他的知名度。

UOJ 中的账号名在数据库中由给定一棵有 $l$ 个节点的 trie 树（以 $1$ 为根）存储。

对于树上的某个点 $i$，定义 $u_i$ 为从根节点到 $i$ 的路径上的字符从浅到深顺次连接得到的字符串（$u_{1}=\varnothing$）。

$u_i$ （$1 < i \le l$）同时是跳蚤的账号名。

超级管理员 Skip 蚤想用如下方式生成自己的账号名 $T$。

给出若干字符串 $s_1,s_2,\dots,s_n$，令 $T=s_{a_1}+s_{a_2}+\dots+s_{a_m}$。

现在，Skip 蚤想知道，对于每一个账号名 $u_i(1 < i \le l)$，在自己的账号名 $T$ 中出现的次数 $ans_i$。

输入第一行包含四个正整数 $l,n,m,w$。

接下来一行包含一个 $l-1$ 个正整数，分别表示 $c_2,c_3,\dots,c_l$，即 trie 树上每个点到父亲的边上的字符。

接下来一行包含 $l-1$ 个正整数，分别表示 $\mathrm{fa}_2,\mathrm{fa}_3,\dots,\mathrm{fa}_l$，即 trie 树上每个点的父亲。

接下来 $n$ 行，每行首先有一个正整数表示 $|s_i|$，然后 $|s_i|$ 个正整数给出 $s_i$。

接下来一行 $m$ 个正整数，分别表示 $a_1,a_2,\dots,a_m$。

输出一行 $l-1$ 个非负整数，分别表示 $\mathrm{ans}_2,\mathrm{ans}_3,\dots,\mathrm{ans}_l$。

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

13 6 3 9 3 1

记 $S=\sum_{i=1}^{n}|s_i|$。

对于所有数据，保证 $1\le l\le 10^5,1\le n\le 100,1\le m\le 10^6,1\le S \le 3 \cdot 10^6,1\le fa_i\le l, 1\le w\le 4\times 10^6$，所有输入的字符 $\in [1,w]$。

保证输入的 $fa$ 构成一棵以 $1$ 为根的树。

子任务编号	$l\le$	$m\le$	$S\le$	$w\le$	trie树形态	分值
$1$	$2000$	$2000$	$2000$	$4\times 10^6$	-	$7$
$2$	$10^5$	$10^6$	$3\times 10^6$	$4\times 10^6$	$fa_i=i-1(1 < i\le n)$	$14$
$3$	$2000$		$3\times 10^6$	$26$	-	$17$
$4$	$10^5$		$5\times 10^5$	$26$		$29$
$5$	$10^5$		$3\times 10^6$	$4\times 10^6$		$33$

时间限制：$3\texttt{s}$

空间限制：$1\texttt{GB}$

Universal Online Judge