Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Distinct List

By shefin · Limits 5s, 256 MB

Byteland has a network of nn computers that forms a tree structure. A tree is a connected graph that has no cycles.

Each computer uu has a special database and special software. The database has initially a list LuL_u. The list LuL_u has only one element AuA_u initially. The software is programmed to do a special task. When a list BB is given to the computer uu’s special software, it starts to iterate through the list BB. For each element BiB_i of the list BB, the software does the following:

  • If the element BiB_i already exists in the list LuL_u the software does nothing. Otherwise, it appends BiB_i to the end of the list LuL_u.

After completing the iteration, the software then sorts the list LuL_u in ascending order. For example, if a list LuL_u is [13][13] initially and we give the lists [13,75,26],[0,7],[0,7,13,25][13, 75, 26], [0, 7], [0, 7, 13, 25] to the software of computer uu one by one, then eventually the list LuL_u will be [0,7,13,25,26,75][0, 7, 13, 25, 26, 75].

To ensure the security of the network, each computer sends a copy of all the lists in its database to its parent computer (if exists) only. When a computer uu gets the lists from a child computer, the computer uu adds the lists to its database and also gives the lists to its special software to update the list LuL_u. Only after receiving all the lists from all the children's computers and updating the list LuL_u accordingly, a computer uu sends a copy of all the lists in its database to its parent computer (if exists).

For each computer uu, you have to tell how many distinct lists are present in its database after completing all the above operations. Two lists are different if either they have different sizes or one list has at least one element that is not present in the other list.


Input starts with an integer T(1T105)T(1\leq T\leq 10^5), the number of test cases.

In each test case, the first line contains an integer n(1n105)n(1\leq n\leq 10^5), the number of computers.
The next line contains nn space-separated integers Ai(0Ai109)A_i(0\leq A_i\leq 10^9), the single initial element of the list LiL_i of computer ii.
The last line of each test case contains nn space-separated integers Pi(1Pin)P_i(1\leq P_i\leq n), the parent computer of computer ii. If computer ii is the root of the tree, PiP_i will be 1-1.

It is guaranteed that the computer network will form a tree structure and the sum of nn over all test cases will not be greater than 10610^6. It is also guaranteed that if n>104n>10^4, then T=1T=1.


In each test case, print nn space-separated integers in a line. The ithi^{th} integer represents the number of distinct lists present in the database of the computer ii.


7 10 15 10
3 1 -1 1
25 25 25
-1 1 1
2 1 3 1
1 1 1


In the first test case, the computer network looks like the below tree where the computer 33 is the root of the tree:

The only list in computer 22’s database is [10][10] which is also the list L2L_2. It is the only distinct list on this computer.
The only list in computer 44’s database is [10][10] which is also the list L4L_4. It is the only distinct list on this computer.
The lists in computer 11’s database are: [7,10],[10],[10][7,10], [10], [10] where the first list is the list L1L_1. The two distinct lists are: [7,10],[10][7,10], [10].

The lists in computer 33’s database are: [7,15,10],[7,10],[10],[10][7,15,10], [7,10], [10], [10] where the first list is the list L3L_3. The three distinct lists are: [7,15,10],[7,10],[10][7,15,10], [7,10], [10].



50% Solution Ratio

serotoninEarliest, 1M ago

serotoninFastest, 2.2s

serotoninLightest, 26 MB

serotoninShortest, 2285B


Login to submit


We will divide the problem into two parts. Part 1: We need to find out the list LuL_uLu​ of each nod...

Toph uses cookies. By continuing you agree to our Cookie Policy.