UnrelatedPaths
2015 TCO 1C · 2015-04-08 · by praveen123
Problem Statement
This problem is about paths on a tree. A path is any sequence of one or more vertices such that all the vertices are distinct and each pair of consecutive vertices is connected by an edge of the tree.
Our tree is a rooted tree with N+1 vertices, labeled 0 through N.
The label of the root is 0.
For each i, the parent of vertex i has a number smaller than i.
You are given the description of the tree: a
The vertex u is an ancestor of the vertex v if u lies on the (only) path that connects v to the root. Note that each vertex is its own ancestor. Also note that the root is an ancestor of all other vertices.
Two paths A and B in our tree are said to be related if path A contains a vertex u and path B contains a vertex v such that one of u, v is an ancestor of the other.
We want to choose many paths in such a way that no two of them will be related. Find and return the largest possible number of pairwise unrelated paths in the given tree.
Constraints
- N will be between 0 and 50, inclusive.
- parent will contain exactly N elements.
- For each i, parent[i] will be between 0 and i, inclusive.
{0, 1, 1, 2, 3}
Returns: 2
The int[] parent tells us the following information: The parent of vertex 1 is vertex 0. The parent of vertex 2 is vertex 1. The parent of vertex 3 is vertex 1. The parent of vertex 4 is vertex 2. The parent of vertex 5 is vertex 3. In this tree it is possible to select two unrelated paths. One possible way of doing so is to select the paths 4-2 and 3-5.
{0, 0, 1, 1, 2, 2}
Returns: 4
{0, 1, 2, 3}
Returns: 1
{0,1,1,2,2,2,4,6,5,0,10,5,12,12,10,4,16,12,5,3,20,12,11,21,9,5,1,20,15,24,6,8,15}
Returns: 17
{0,1,1,1,1,0,2,5,1,6,7,10,5,10,8,5,16,14,8,14,4,14,15,21,0,24,11,1,9,18,13,20,6,28,19,28,14,11,38,26,25,10,23,43}
Returns: 19
Submissions are judged against all 71 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class UnrelatedPaths with a public method int maxUnrelatedPaths(vector<int> parent) · 71 test cases · 2 s / 256 MB per case