A85760."CTSC2018" dictionary tree
NOI/NOI+/CTSC
Add to question list
Question correction
Pass rate:
0%
Time limit:
5.00s
Memory limit:
512MB
Question description
Access Globe has severalIncrementsequence of positive integers. He wrote down the decimal representation (without leading zeros) of each positive integer in these sequences of positive integers, with a comma between two adjacent integers.,separated. Access Globe treats this sequence as a sequence
consisting ofStrings composed of numbers and commas, and then use a Trie tree to store these strings. You don't need to know what a Trie tree is. You only need to know that the Trie obtained by Access Globe is a rooted tree with node 0 as the root. There is a character on each edge, and from the
root to each
0
−
9
0−9leaf nodeThe string formed by concatenating the characters on the edge of the path in sequence is an increasing sequence of positive integers written by him.
Cute little Tommy decided to tamper with the Trie tree. He first deletes some characters on the edges of the Trie, and then fills in other characters. In order not to be discovered, Tommy must ensure that the modified Trie still satisfies the above properties, that is, the string formed by
sequentially splicing the characters on the edges on the path from the root to each leaf node is an increasing sequence of positive integers separated by commas, and each positive integer has noLeading zeros。
Now that Tommy has deleted some characters on the side, please help him complete the "fill in the characters" operation. If there are multiple solutions, please output the solution with the smallest lexicographic order.
Input format
The input file contains multiple sets of data. The first line of the entire file is an integer., represents the number of data groups. For each set of data:
T
T
The first line contains a string of length
n
nof, including only
0
0arrive
9
9、,and?string, no.
i
iintegers represent connected nodes
i
iparent and node
i
iThe characters on the side of?Indicates that the characters on this side have been deleted;
The second line contains
n
ninteger, no.
i
iintegers represent nodes
i
ithe parent node of
f
i
f
i
,ensure
0
≤
f
i
<
i
0≤f
i
<i。
Output format
outputOK. For each set of data, output a length ofA string representing the lexicographically smallest way to fill in the characters of each dot in the question mark, No.integers represent nodescharacters.
T
T
n
n
i
i
i
i
If there is no legal way to fill in, please outputfailed。
Input and output samples
Input #1
copy
1
2,?3,2?71?4420?2641?
0 1 2 3 4 5 6 7 8 6 10 7 4 4 14 3 2 1 1 0
Output #1
copy
2,13,207104420026411
Instructions/Tips
fordata,, for each set of data ，
20
%
20%
T
≤
10
T≤10
n
≤
80
n≤80?The number does not exceed；
8
8
FOR ADDITIONALDATA,, FOR EACH SET OF DATA， ；
10
%
10%
T
≤
20
T≤20
N
≤
80
N≤80
F
I
i
−
1
f
i
=i−1
FOR ADDITIONALDATA,；
20
%
20%
F
I
i
−
1
f
i
=i−1
For additionaldata,；
10
%
10%
n
≤
80
n≤80
For all data,, for each set of data。
T
≤
100
T≤100
n
≤
200
n≤200
