- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: March, 2016 -
**Competitors who opened the problem**: 382 -
**Competitors who submitted a solution**: 326 -
**Number of correct solutions**: 275 -
**Accuracy (percentage correct vs those who opened)**: 72.0% -
**Average Correct Time**: 18 minutes, 2 seconds. -
**tests.sh** -
**answers.txt**

- 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*C*distinct components. Return the maximum value of_{i}*C*for any_{i}*i*. - The topcoder constraints cap
*T's*size at 99 elements, but I'm going to raise that constraint to 10,000.

- 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

*C*by removing node 0_{i} - Example 1: T = { 0, 1, 2, 3 }. The answer is 2. Here is a tree:
2 / \ 1 3 / \ 0 4

You get the maximum

*C*by removing nodes 1, 2 or 3._{i} - 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.

You don't need to worry about the structure of the tree -- whether one node is the parent of another. Let's take example 0 as an example. All of the following trees correspond to the specified edges:

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

And the answer is the same regardless of how you view the parent/child relationship in the
tree. So the answer here is to maintain a vector *E*, one per node in the tree.
*E[i]* should contain the number of edges coming out of node *i*.
The maximum value of *E[i]* is the answer.

You can create *E* very simply by running through *T*. Each value of *T[i]*
corresponds to the edge *(T[i],i+1)*, so for each value of *T* you increment two
values of *E*. Then calculate the maximum.