![]() |
||||||||||
|
||||||||||
TrieTime Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 774 Accepted Submission(s): 110 Problem Description Little Bob studied Trie in Data Structure class. He learned that Trie is a rooted tree to store some strings. There is a character on each edge of a Trie. (In this problem, the valid characters are lowercase Latin letters.) Bob draws a Trie with n nodes, and the nodes are numbered with integers from 1 to n. The number of the root node is always 1. He uses Si to denote the string concatenated with characters on the path from the root to node i. It can be seen that S1 is the empty string. Furthermore, for a set P ![]() ![]() Bob defines a kind of trait on this Trie. The trait can be described with a set P ![]() ![]() Bob also defines a mapping f on P ![]() ![]() ![]() Initially, there is no traits been defined. Bob will add traits whenever he wants. Let Di denote the number of traits that Si has until now. Note that Di may change when a new trait is added. Besides adding new traits, Bob may also ask you something about his Trie. In each query, Bob will give you a set P ![]() ![]() Input The first line contains an integer T (T ≤ 5), denoting the number of the test cases. For each test case, the first line contains an integer n(1 ≤ n ≤ 105). From the second to the n-th line, this n - 1 lines describe Bob' s Trie. The i-th line contains an integer u(u < i), and a lowercase letter c, which means that the father of node i is node u and the character on that edge is c. We ensure that for each node i, letters on edges connecting i and its children are all different. The next line contains an integer m(m ≤ 105), which means there are m operations. The next m lines describe all operations. In each line, the first integer indicates the type of this operation. 1 means Bob will add a new trait and 2 means Bob is asking you a question. The second integer k is the size of set P , and the next k integers are the elements of P. We ensure that these k integers are different, and they are all between 1 and n. The total size of the m sets will not be larger than 5·105. Output For each test case, output the answer for each query operation, one answer in a line. Sample Input
Sample Output
Source | ||||||||||
|