James S. Plank

Tue Nov 2 15:46:24 EDT 2021

In case Topcoders Servers are Down

• You are given the definition of a tree with a vector of integers, T.
• There are n+1 nodes in the tree, numbered 0 through n.
• The vector T has exactly n entries.
• If T[i] = x, then there is an edge between nodes i+1 and x.
• You are guaranteed that T defines one connected tree.
• Suppose you remove a node i from the tree, and all of the edges from and to i. That will leave Ci distinct components. Return the maximum value of Ci for any i.
• The topcoder constraints cap T's size at 99 elements, but I'm going to raise that constraint to 10,000.

Examples

• Example 0: T = { 0,0,0 }. The answer is 3. Here is one tree that fits the definition:

 ``` 0 /|\ / | \ 1 2 3 ```

You get the maximum Ci by removing node 0

• Example 1: T = { 0, 1, 2, 3 }. The answer is 2. Here is a tree:

 ``` 2 / \ 1 3 / \ 0 4 ```

You get the maximum Ci by removing nodes 1, 2 or 3.

• Example 2: T = { 0, 0, 2, 2 }. The answer is 3.
• Example 3: T = { 0, 0, 0, 1, 1, 1}. The answer is 4.
• Example 4: T = { 0, 1, 2, 0, 1, 5, 6, 1, 7, 4, 2, 5, 5, 8, 6, 2, 14, 12, 18, 10, 0, 6, 18, 2, 20, 11, 0, 11, 7, 12, 17, 3, 18, 31, 14, 34, 30, 11, 9}. The answer is 5.

Testing yourself

 ``` 0 1 2 3 /|\ | | | 1 2 3 0 0 0 / \ / \ / \ 2 3 1 3 1 2 ```