While wandering through a forest, you have stumbled upon a mysterious dynamic apple tree! This tree can be thought of as a set of connected junctions, numbered from to , such that there is exactly one path between any two junctions. The root of the tree is at junction (which is at the bottom), and each junction has at most one branch connecting it to a junction below it, which we will call for all junctions . The only junction without branch connecting it to a junction below it is junction , the root of the tree.
You will pick a junction and collect all apples from the root up to, and including the junction you stop at, before climbing back down the tree. Unfortunately for you, of your friends have decided to follow you to this apple tree and also want to collect apples. For simplicity, we will number your friends from to , and you will be assigned number .
There is exactly one apple at each junction, but since this is a dynamic tree, it has a special property where each apple regrows exactly minutes after it is picked. Note that an apple can be picked the same second it regrows.
Every minute, one of your friends (or you) will climb up the tree, collect some apples, and climb back down the tree. They will go in order of their number from to . Each of you will do this once. Assuming each friend maximizes the total number of apples they will collect, you want to know the number of apples each of them will end up with.
Constraints
For this question, Python users are recommended to use CPython over PYPY.
For this problem, you will be required to pass all the samples in order to receive any points. In addition, you must pass all previous subtasks to earn points for a specific subtask.
Subtask  Points  

 
 

For all subtasks:
for all
Input Specification
The first line contains 3 integers, , , .
The last line contains integers, describing the tree structure. The integer contains the value , indicating that junction is connected to junction .
Output Specification
This problem is graded with an identical
checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n
character and that there are no trailing spaces.
Output a single line containing space separated integers. The integer is the number of apples collected by the person.
Sample Input
6 3 2
1 2 2 3 3
Sample Output
4 1 4
Sample Explanation
At the first minute, person can climb up to junction and collect apples.
At the second minute, person can climb up to junction and collect apple.
At the third minute, the apples at junctions , , , and regrow. Person can climb up to junction and collect apples.
Comments
SPOILER ALERT
I am so happy that I finally solved it with Segment Tree + lazy. This problem is a really good one to practice Segment tree in a graph. I would recommend to you guys that already solved it in other ways to give it a try!