TransformTheTree | Topcoder Archive

Problem Statement

You have a tree consisting of N nodes. The nodes are conveniently numbered 0 through N-1. You are given an int[] parents that consists of N-1 elements. For each 1 ≤ i < N, the parent of node i is node parents[i-1].

Your goal is to transform the tree into a path. In order to accomplish that you are allowed to use the following operation multiple times:

Choose an edge {u, v}.
Remove the edge {u, v} obtaining two trees T1 and T2 in this way -- T1 containing u and T2 containing v.
Choose any node w from T1 and any node z from T2.
Add the edge {w, z}.

Return the minimum number of operations needed to transform the given tree into a path.

Definition

Class:: TransformTheTree
Method:: countCuts
Parameters:: int[]
Returns:: int
Method signature:: int countCuts(int[] parents)
(be sure your method is public)

Constraints

N will be between 1 and 50, inclusive.
parents will contain exactly N â 1 elements.
For each i, parents[i] will be between 0 and i, inclusive.

Examples

```
{0, 0, 1, 2, 1}
```
```
Returns: 1
```
Initially, the tree contains the following edges: 0-1, 0-2, 1-3, 2-4, and 1-5. This tree is not a path, but we can change it into a path in a single operation. One optimal solution looks as follows: Remove the edge 1-5. This produces two trees: T1 is a path on five vertices and T2 is a single isolated vertex. Then, add the edge 4-5. Doing so produces the path 3-1-0-2-4-5.
```
{0, 0, 0, 0, 0, 0}
```
```
Returns: 4
```
One optimal sequence of operations looks as follows: Cut the edge 0-3, add the edge 2-3. Cut the edge 0-2, add the edge 1-2. Cut the edge 0-6, add the edge 5-6. Cut the edge 0-5, add the edge 4-5. After applying these operations the resulting tree is 3-2-1-0-4-5-6.
```
{0, 0, 1, 2, 3, 4, 5, 6}
```
```
Returns: 0
```
The given tree is already a path.
```
{}
```
```
Returns: 0
```
```
{0, 1, 2, 3, 2, 5, 0, 7, 8, 9, 8, 11}
```
```
Returns: 2
```
The following provides the minimum number of operations: Cut the edge 2-5, add the edge 6-10. Cut the edge 8-9, add the edge 5-12.

{0, 1, 2, 0, 4, 5, 6, 4, 5, 6, 0, 11, 12}

Returns: 2

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.