P11840 [USACO25FEB] Vocabulary Quiz S

Bessie 正在帮助 Elsie 准备她即将到来的词汇测验。要测验的单词将从 $M$ 个不同单词的词库中抽取，其中词库里没有一个单词是另一个单词的前缀。 当词库非空时，Bessie 将从词库中选择一个单词，将其从词库中移除，并从左到右逐个字符地读给 Elsie。Elsie 的任务是在她能够唯一确定该单词时告诉 Bessie，此后 Bessie 将停止朗读。 Bessie 已经决定按顺序 $w_1,w_2,\dots,w_M$ 朗读单词。如果 Elsie 尽可能快地回答，Bessie 将朗读每个单词的多少个字符？ 这些单词以一种压缩格式给出。我们将首先定义 $N+1$（$1\le N\le 10^6$）个不同的单词，然后词库将由其中所有不作为另一个单词前缀的单词组成。这些单词定义如下： - 初始时，第 $0$ 个单词为空字符串。 - 然后对于每一个 $1\le i\le N$，第 $i$ 个单词将等于第 $p_i$ 个单词在末尾加上一个额外的字符（$0\le p_i

输入的第一行包含 $N$，其中 $N+1$ 是以压缩格式给出的单词的数量。 以下一行包含 $p_1,p_2,\dots,p_N$，其中 $p_i$ 表示第 $i$ 个单词是通过取第 $p_i$ 个单词并在末尾添加一个字符形成的。 令 $M$ 为不是某个其他单词前缀的单词数量。以下 $M$ 行将包含 $w_1,w_2,\dots,w_M$，表示第 $w_i$ 个单词将是第 $i$ 个被朗读的单词。输入保证朗读的单词形成词库中单词的一个排列。

输出 $M$ 行，其中第 $i$ 行包含 Bessie 对第 $i$ 个单词朗读的字符数量。

样例 1 解释： 有 $6$ 个单词编号为 $0 \dots 5$。单词 $5$ 是唯一一个不是另一个单词的前缀的单词，因此它是词库中唯一的单词。一般地说，一旦库中仅剩下一个单词，Elsie 就不再需要任何字符以确定它。 样例 2 解释： 词库由单词 $2$，$3$ 和 $4$ 组成。 Elsie 需要两个字符来确定单词 $4$，因为单词 $3$ 和 $4$ 的第一个字符相同。 一旦 Bessie 朗读了单词 $3$ 的第一个字符，Elsie 就有了足够的字符来唯一确定它，因为单词 $4$ 已经被朗读。 - 测试点 $4\sim 5$：所有单词的长度均不超过 $20$。 - 测试点 $6\sim 10$：词库中所有单词的长度之和不超过 $10^7$。 - 测试点 $11\sim 18$：没有额外限制。