Vocabulary Quiz

题目描述

贝西正在帮助艾尔西准备即将到来的词汇测验。要测试的单词将从一个包含 $M$ 个互不相同单词的词库中抽取，并且词库中的任意单词都不是另一个单词的前缀。 当词库非空时，贝西会从词库中选取一个单词，将其从词库中移除，并从左到右逐字符读给艾尔西听。艾尔西的任务是在她能够唯一确定该单词时告诉贝西，随后贝西将停止继续朗读。 贝西已经决定按照 $w_1,w_2,\dots,w_M$ 的顺序读出词库中的单词。如果艾尔西总是尽可能快地作答，那么贝西对每个单词会读出多少个字符？ 这些单词以压缩格式给出。我们先定义 $N+1$（$1\le N\le 10^6$）个互不相同的单词，然后词库由所有那些不是另一个单词前缀的单词组成。单词的定义如下： 初始时，第 $0$ 个单词为空串。 接着对每个 $1\le i\le N$，第 $i$ 个单词等于第 $p_i$ 个单词再在末尾追加一个字符（$0\le p_i<i$）。这些字符的选择保证所有 $N+1$ 个单词互不相同。

输入格式

第一行包含整数 $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$ 行包含贝西对第 $i$ 个单词读出的字符数。

5
0 1 2 3 4
5

0

4
0 0 1 1
4
3
2

2
1
0

4
0 0 1 1
2
3
4

1
2
0

提示

有 $6$ 个单词，编号为 $0\dots 5$。单词 $5$ 是唯一一个不是其他单词前缀的单词，因此它是词库中唯一的单词。一般而言，当词库中只剩下一个单词时，艾尔西不需要任何字符就能识别它。 词库由单词 $2$、$3$ 和 $4$ 组成。 艾尔西需要两个字符才能识别单词 $4$，因为单词 $3$ 与单词 $4$ 的首字符相同。 当贝西读出单词 $3$ 的第一个字符后，艾尔西已经有足够的字符来唯一识别它，因为单词 $4$ 已经被读过了。 计分： 输入 4-5：没有单词长度超过 $20$。 输入 6-10：词库中所有单词长度之和不超过 $10^7$。 输入 11-18：无额外限制。 题目来源：Benjamin Qi

标签: USACO|2025|Silver

来源

USACO|2025|Silver