IMPER - Imperialism

no tags 

Original statement in spanish at

The ambition of conquest and expansion is a very well known disease in planet Earth... and also in the entire universe.

In planet “Imperius” several fortresses have been built one at a time and each one of them but the first was connected at the moment of its construction to a previously built fortress by a direct path, for commercial purposes.

Imperius was becoming one of the most peaceful and prosperous planet in the universe, until they built no more fortresses. At that moment, N different empires emerged (numbered from 1 to N), each one of them dominating a different fortress. And the thirst of conquest took Imperius. Thus, every year, exactly one of the living empires conquers every neighbor empire, and dominates every fortress belonging to them. Two empires are considered neighbors if there exist two fortresses joined by a path, each one dominated by one different empire of these two.

Eventually a single empire will dominate every fortress. Your task is to find the minimum number of years such that this can happen.

As an example, on the left side of the figure below a possible scenario in which six fortresses are initially dominated by six different empires is shown. Each fortress is tagged with the identification number of the empire dominating it. If empire 2 conquered every neighbor on the first year, the the situation would be as in the central figure. Finally, if empire 5 conquered his neighbor empires, it would end up dominating every fortress, as seen on the right side of the figure.



The input contains several test cases. Each test case is described in two lines. The first line contains an integer N (2 <= N <= 104) representing the number of fortresses in planet Imperius. The next line contains N-1 integers P_i indicating that the fortress i+1 was connected to fortress P_i (1 <= P_i <= i for 1 <= i <= N-1). The last line of the input contains a single -1 and should not be processed as a test case.


For each test case output a single line with an integer representing the minimum number of years such that a single empire may dominate every fortress.



1 2 2 4 5
1 1 3 3 4 4
1 2 2 2 2



hide comments
Juan: 2017-04-02 23:46:05

@Mushegh for the second test, just expand twice the third node, it has a distance of max 2 steps to every other node

Mushegh: 2014-05-14 21:18:27

please explain the testcase 2

Last edit: 2014-05-14 21:18:41
The Ultimate Fire Mage’s Grandfather: 2012-08-14 07:41:36

Think it easy. :)

yzh: 2011-10-29 01:14:43

Nice title.

Added by:Pablo Ariel Heiber
Time limit:0.600s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2011