Practice on Toph

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

Village Fair 2

Limits: 5s, 512 MB

There are N houses in a village far away from here. They are numbered from 1 to N. For this problem lets assume the houses each can accommodate an infinite number of people.

From each house there is a directed path to exactly one other house. One of the houses is a grand house. There is a fair going on currently in the grand house. From this house there is no exit, and everybody can enjoy the festival here. It is guaranteed that there is exactly one simple way from each house to the grand house. The house numbered 1 is the grand house.

Initially there is a little kid in each of the houses of the village. Each kid has some non-negative amount of joy. They are all pretty excited about the fair. Every kid from their house starts their journey to the grand house. When they go from a house to some other house, their joy changes by some amount. This change depends on the path. If at any point in time some kid’s joy value becomes negative he returns to home. This kid is not counted in later part.

Now for each house, you have to count the number of distinct non-negative joy values that will come to this house at some point in time. Note that if two or more persons come to a house with the same joy value, it will be counted only once.

See the sample explanation for details.

Input

The first line contains the number of test cases in the input T (1 ≤ T ≤ 10). Then T sets of of input follows.

You are given an integer N (1 ≤ N ≤ 100000) in the first line. The next line will contain N non-negative integers, the initial joy value of the kids in the houses.

The next line also contains N integers, where the kth integer is the ID of the house where the kids can go to from the kth house or 0 if it is the grand house.

The fourth line will contain N integers, the amount of change of joy that will occur if a person goes through the path from starting at kth house or 0 if it is the grand house.

No absolute values of joy or path is greater than 1000.

Output

For each test cases first print “Case #:” in one line (where “#” is the case number, starting from 1). Then print N lines, each containing the number of distinct non-negative joy values that will come to this house at some point in time.

Samples

InputOutput
2
5
7 3 2 5 1
0 1 1 3 3
0 4 1 0 4
2
3 2
0 1
0 -5
Case 1:
3
1
2
1
1
Case 2:
1
1

If you code in any language other than C/C++, then do it in your own risk. There is no guarantee that it will pass, even though it might be the correct solution and have the desired complexity. The data set is huge. Please use fast I/O methods.

In the sample, initially each house will contain the kids with joy {7, 3, 2, 5, 1}. The first kid always stays in the grand house. The second kid will go to the grand house with joy 7. The 3rd kid will go to the grand house with joy 3. The fourth kid will go to 3rd house with joy 5 and from there he will make it to grand house with 6 joy. Same goes for 5th person.

The first house will see {7, 7, 3, 6, 6}. The second house will see {3}. The third house will see {2, 5, 5} The fourth house will see {5} and the fifth house will see {1}.

So the number of distinct joy values of each house is {3, 1, 2, 1, 1}.

Author
  • nfssdq's Avatar

    nfssdq

    Nafis was a student of Jahangirnagar University, a die-hard programming contestant. His team became the champion in ACM-ICPC Dhaka Regional 2015. He participated in the 39th and 40th ACM-ICPC World Finals.
Discussion