Do you remember the politicians having a LAN party during conference sessions? Well, this time they managed to get a virus on all of their PCs. Fortunately the great antivirus software of ESET managed to clean up the mess, but now the politicians want to know who to blame for the virus. Hence the network administrator has to find the machine which started to spread the virus. | ![]() |
As you may remember the network topology is a tree, and PCs are directly connected to each other. It turns out the virus can only spread to neighboring machines and by examining the logs of a machine one can determine which directly connected PC it got the virus from (or if the machine was the source of the virus itself). So after checking a machine we either find the virus source or know which connected subtree contains it.
Unfortunately politicians are not going to let the admin look into their PCs easily, as they might keep some highly sensitive information there.
After a long (and tedious) debate the politicans arrived at the following consensus: A virus hunting plan must be made to find the source of the virus with the least number of checks possible in the worst case.
The format of the virus hunting plan is already determined: it simply assigns a non-negative integer to each machine. First the PC with the highest assigned number is checked. If it was the source of the virus then the hunting is finished, otherwise the algorithm continues in the appropriate subtree, where the checked PC got the virus from. In this subtree, again, the PC with the highest assigned number is checked. This checking procedure goes on until the source of the virus is found.
The politicians want you to give them a virus hunting plan that minimizes the required number of checks in the worst case, considering every possible PC as the source of the virus.
The first line of the input contains N the number of machines. Machines are numbered from 0 to N-1.
The next line describes the network tree by N-1 numbers: the ith number gives a neighbor of the (i+1)th machine (i goes from 0 to N-2, and the ith number is at most i).
The output is one line with N numbers. The ith number is the integer the virus hunting pla1n assigns to the ith machine (i goes from 0 to N-1).
Note that during the virus hunting process there always must be only one maximal number assigned to the remaining possible virus sources, so the decision is uniquely determined by the plan.
You should normalize the plan in the following way: the smallest number assigned in the plan should be 0, and the highest number should be the worst case number of checks needed. (So in the worst case the assigned numbers of the consecutively checked machines always decrease by one).
Only an optimal plan is accepted.
7 0 1 2 3 4 3
0 1 0 2 1 0 0
Each solved input is worth 100 points.