## Wesley's Anger Contest 1 Problem 3 - A Dynamic Tree Problem

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

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.

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.