TransformTheTree
TCC India Online · 2017-07-25 · by boba5551
Problem Statement
You have a tree consisting of N nodes. The nodes are conveniently numbered 0 through N-1. You are given an
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.
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.
{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.
Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TransformTheTree with a public method int countCuts(vector<int> parents) · 58 test cases · 2 s / 256 MB per case