SRM 686, D2, 250-Pointer (TreeAndVertex)

James S. Plank

Tue Nov 2 15:46:24 EDT 2021

In case Topcoders Servers are Down


Examples


Testing yourself

Standard files: tests.sh and answers.txt.

Hints

If you remove vertex i, and there are c edges coming out of i (both children and parent edges), then you will be left with c components. So this problem is a straightforward matter of counting the number of edges coming out of each vertex.

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.