SRM 686, D2, 250-Pointer (TreeAndVertex)

James S. Plank

Tue Nov 2 15:46:24 EDT 2021

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

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 C_i distinct components. Return the maximum value of C_i 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 C_i 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 C_i 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

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.