Problems
Bessie is helping Elsie with her upcoming vocabulary quiz. The words to be tested will be drawn from a bank of M distinct words, where no word in the bank is a prefix of another word.
While the bank is nonempty, Bessie will select a word from the bank, remove it, and read it to Elsie one character at a time from left to right. Elsie’s task is to tell Bessie as soon as she can uniquely identify the word, at which point Bessie stops reading.
Bessie has already decided to read the words from the word bank in the order w₁, w₂, …, w_M. If Elsie answers as quickly as possible, how many characters of each word will Bessie read?
The words are provided in a compressed format. First, we define N+1 distinct words, and then the word bank consists of all those words that are not a prefix of another word. The words are defined as follows:
Initially, the 0th word is the empty string.
Then, for each 1 ≤ i ≤ N, the i-th word is formed by taking the pᵢ-th word and appending an additional character at the end (0 ≤ pᵢ < i). The characters are chosen so that all N+1 words are distinct.
Input
The first line contains an integer N, where N+1 is the number of words given in the compressed format.
The next line contains N space-separated integers: p₁, p₂, …, p_N, where pᵢ indicates that the i-th word is formed by taking the pᵢ-th word and appending a single character.
Let M be the number of words that are not a prefix of some other word (i.e., the words in the word bank).
The next M lines contain w₁, w₂, …, w_M, meaning that the wᵢ-th word (from the compressed list) will be the i-th word read. It is guaranteed that w₁, …, w_M form a permutation of the words in the word bank.
Output
For each test case, output M lines. The i-th line should contain the number of characters that Bessie reads for the i-th word.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 20 | No word has a length greater than 20. |
| #2 | 30 | The sum of the lengths of all words in the word bank does not exceed 10⁷ |
| #3 | 50 | No additional constraints. |
Example #1
5
0 1 2 3 4
5
0
There are 6 words (labeled 0 through 5) given in the compressed format. Among these, the word bank consists only of words that are not a prefix of any other word. In this case, only word 5 qualifies, so the word bank contains just one word. When only one word remains in the bank, Elsie does not need to hear any characters to identify it, so Bessie reads 0 characters.
Example #2
4
0 0 1 1
4
3
2
2
1
0
The word bank consists of words 2, 3, and 4 (from the compressed list).
For word 4, since it shares its first character with word 3, Elsie needs to hear 2 characters to uniquely identify it.
For word 3, since word 4 has already been read, Elsie needs only 1 character.
Finally, when only one word remains in the bank, Elsie needs 0 characters.
Example #3
4
0 0 1 1
2
3
4
1
2
0
The word bank consists of words 2, 3, and 4, and the order in which they are read is given as in Example 3.
The first word read (word 2) is uniquely identified after hearing 1 character.
The second word (word 3) requires 2 characters to be uniquely identified.
The final word, being the only one left in the bank, requires 0 characters.
You must sign in to write code.