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 in the bank.
While the bank is nonempty, Bessie will select a word from the bank, remove it from the bank, and read it to Elsie one character at a time from left to right. Elsie's task is to tell Bessie once she can uniquely identify it, after which Bessie will stop reading.
Bessie has already decided to read the words from the word bank in the order w1,w2,…,wM. If Elsie answers as quickly as possible, how many characters of each word will Bessie read?
The words are given in a compressed format. We will first define N+1 (1≤N≤ 106 ) distinct words, and then the word bank will consist of all those words that are not a prefix of another word. The words are defined as follows:
Initially, the 0th word will be the empty string.
Then for each 1≤i≤N, the ith word will be equal to the pith word plus an additional character at the end (0≤pi<i). The characters are chosen such that all N+1 words are distinct.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N, where N+1 is the number of words given in the compressed format.
The next line contains p1,p2,…,pN where pi represents that the i-th word is formed by taking the pi-th word and adding a single character to the end.
Let M be the number of words that are not a prefix of some other word. The next M lines will contain w1,w2,…,wM, meaning that the with word will be the ith to be read. It is guaranteed that the words to be read form a permutation of the words in the word bank.
OUTPUT FORMAT (print output to the terminal / stdout):
Output M lines, where the ith line contains the number of characters of the ith word that Bessie reads.
SAMPLE INPUT:
5
0 1 2 3 4
5
SAMPLE OUTPUT:
0
There are 6words labeled 0…5. Word 5 is the only one that is not a prefix of another word, so it is the only one in the bank. In general, once only one word is left in the bank, Elsie won't need any characters to identify it.
SAMPLE INPUT:
4
0 0 1 1
4
3
2
SAMPLE OUTPUT:
2
1
0
The bank consists of words 2, 3, and 4.
Elsie needs two characters to identify word 4 since words 3 and 4 share their first character in common.
Once Bessie reads the first character of word 3 , Elsie has enough characters to uniquely identify it, since word 4 was already read.
SAMPLE INPUT:
4
0 0 1 1
2
3
4
SAMPLE OUTPUT:
1
2
0
SCORING:
Inputs 4-5: No word has length greater than 20.
Inputs 6-10: The sum of the lengths of all words in the word bank does not exceed 107.
Inputs 11-18: No additional constraints.
Problem credits: Benjamin Qi
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
