Statistics

Problem Statement for "UnrelatedPaths"

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 int[] parent with N elements. For each i, the vertex parent[i] is the parent of the vertex i+1.

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.

Definition

Class:
UnrelatedPaths
Method:
maxUnrelatedPaths
Parameters:
int[]
Returns:
int
Method signature:
int maxUnrelatedPaths(int[] parent)
(be sure your method is public)

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.

Examples

  1. {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.

  2. {0, 0, 1, 1, 2, 2}

    Returns: 4

  3. {0, 1, 2, 3}

    Returns: 1

  4. {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

  5. {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

  6. {}

    Returns: 1

  7. {0}

    Returns: 1

  8. {0,1}

    Returns: 1

  9. {0,0,2}

    Returns: 2

  10. {0,1,2,2}

    Returns: 2

  11. {0,0,2,3,2}

    Returns: 3

  12. {0,1,1,3,4,2}

    Returns: 2

  13. {0,0,1,2,0,0,4}

    Returns: 4

  14. {0,0,1,2,1,4,0,6}

    Returns: 4

  15. {0,0,2,3,2,4,5,6,3}

    Returns: 4

  16. {0,1,1,1,2,2,5,3,6,9}

    Returns: 4

  17. {0,1,0,1,4,4,6,6,7,0,2}

    Returns: 6

  18. {0,0,2,3,0,2,1,2,3,9,5,2}

    Returns: 7

  19. {0,0,1,3,0,3,0,6,3,9,5,3,9}

    Returns: 8

  20. {0,1,0,3,0,5,4,5,8,3,3,7,2,9}

    Returns: 6

  21. {0,1,1,3,4,3,3,2,0,0,6,10,3,12,10}

    Returns: 8

  22. {0,0,2,0,3,1,5,5,1,1,8,8,8,2,2,15}

    Returns: 10

  23. {0,1,1,0,2,4,6,6,7,7,2,11,6,13,8,1,6}

    Returns: 9

  24. {0,0,1,1,3,5,0,0,2,8,5,2,10,7,13,15,4,17}

    Returns: 7

  25. {0,0,1,1,4,5,1,4,6,1,2,5,7,10,8,10,11,5,12}

    Returns: 9

  26. {0,1,0,2,3,3,6,0,2,9,4,1,8,12,4,11,5,15,18,14}

    Returns: 7

  27. {0,1,0,3,2,1,4,0,6,3,1,1,12,9,3,10,4,0,6,8,17}

    Returns: 11

  28. {0,0,0,1,0,2,0,7,7,5,9,9,8,12,0,10,13,10,8,12,6,20}

    Returns: 11

  29. {0,1,1,3,3,3,0,5,6,8,0,0,1,2,2,8,3,14,3,8,6,9,7}

    Returns: 14

  30. {0,1,1,1,1,4,1,4,1,6,5,9,12,6,9,14,14,16,7,13,11,15,3,20}

    Returns: 10

  31. {0,1,0,0,0,5,6,6,2,7,3,6,2,0,13,15,3,8,13,2,11,18,11,21,3}

    Returns: 13

  32. {0,0,0,3,3,1,6,6,3,3,0,10,1,3,9,3,5,8,15,9,4,12,0,10,6,14}

    Returns: 15

  33. {0,0,0,0,1,5,2,6,8,7,7,8,2,13,4,6,0,17,8,18,10,14,11,1,6,6,24}

    Returns: 13

  34. {0,0,0,3,2,3,1,2,7,4,0,11,1,12,4,2,10,9,2,14,13,17,10,20,23,7,23,0}

    Returns: 14

  35. {0,1,0,0,2,5,0,0,8,4,8,0,1,7,3,3,15,12,11,7,11,20,15,23,19,21,1,4,1}

    Returns: 15

  36. {0,0,1,2,1,2,2,1,6,8,4,7,0,11,9,12,10,3,2,0,17,2,15,6,6,10,5,0,20,5}

    Returns: 15

  37. {0,1,1,2,0,2,3,7,6,0,9,6,4,1,5,9,11,5,17,5,18,5,21,6,8,2,3,25,25,24,16}

    Returns: 15

  38. {0,1,2,0,2,0,4,3,4,0,10,1,4,11,6,2,9,1,9,2,3,2,18,2,15,25,25,23,24,12,16,20}

    Returns: 16

  39. {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

  40. {0,1,0,2,4,5,5,6,3,9,8,1,9,12,6,11,0,8,15,18,2,19,11,8,0,22,17,16,1,10,2,2,21,22}

    Returns: 16

  41. {0,0,2,1,3,3,3,2,3,2,9,8,10,2,12,10,7,10,10,10,17,19,20,6,19,3,18,16,7,10,14,27,14,14,34}

    Returns: 18

  42. {0,1,2,3,2,0,2,5,0,0,1,0,5,13,10,0,3,3,18,19,3,1,1,10,3,22,20,14,2,20,15,0,15,25,25,35}

    Returns: 22

  43. {0,1,1,3,2,2,0,5,1,8,2,1,10,3,8,5,12,14,12,2,20,14,12,5,10,17,13,4,3,13,0,29,23,17,22,5,30}

    Returns: 21

  44. {0,1,1,0,3,5,2,4,0,0,1,0,11,8,7,3,11,3,12,6,1,21,4,1,14,23,10,21,27,14,23,1,27,23,24,15,4,13}

    Returns: 20

  45. {0,1,0,0,4,3,0,4,2,5,0,9,4,2,0,6,13,4,8,15,12,16,21,18,17,20,11,11,11,12,14,17,28,7,29,35,12,23,1}

    Returns: 16

  46. {0,1,2,3,1,0,3,7,8,3,4,11,2,5,9,0,1,5,11,14,10,16,6,6,19,16,10,6,24,6,9,8,2,10,8,19,24,21,8,11}

    Returns: 24

  47. {0,1,2,0,4,2,1,2,1,7,6,4,0,0,8,3,4,7,18,7,10,11,11,21,23,14,21,0,18,7,28,19,29,26,7,8,11,37,20,26,12}

    Returns: 21

  48. {0,0,2,2,4,3,5,5,4,5,3,3,11,3,5,8,7,3,7,7,7,5,21,22,0,12,17,11,12,6,27,29,31,29,32,30,2,19,33,2,6,28}

    Returns: 22

  49. {0,1,1,1,1,5,4,7,4,4,10,9,3,7,1,8,12,4,7,10,16,13,20,5,5,9,13,23,5,5,7,8,21,29,19,5,3,2,16,35,38,39,26}

    Returns: 22

  50. {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

  51. {0,0,1,3,1,4,0,7,7,2,1,10,6,6,3,3,4,16,17,5,9,7,2,2,23,13,3,1,7,12,18,19,31,33,15,4,29,16,28,3,23,11,13,28,20}

    Returns: 22

  52. {0,0,2,1,3,2,6,3,7,8,8,3,12,6,3,14,4,3,4,11,20,4,19,23,2,23,6,24,13,21,6,1,23,2,7,2,14,33,21,31,0,19,21,36,27,9}

    Returns: 25

  53. {0,0,0,2,1,0,0,0,6,0,9,11,8,12,4,4,14,8,9,12,1,9,21,19,13,11,26,24,15,4,17,28,30,22,22,0,29,20,36,25,14,23,34,25,29,19,24}

    Returns: 22

  54. {0,0,1,1,2,3,3,3,2,3,9,4,6,5,5,13,1,15,0,6,1,6,6,18,21,0,12,1,24,17,13,11,30,24,26,34,30,1,0,11,37,36,28,1,21,0,35,34}

    Returns: 26

  55. {0,0,1,3,4,4,1,7,8,7,7,7,12,5,9,10,6,16,14,19,15,9,15,8,9,19,3,25,18,2,8,1,15,22,10,14,35,8,24,29,28,28,38,6,31,42,28,43,19}

    Returns: 23

  56. {0,1,2,1,3,2,2,7,8,8,1,10,4,5,7,8,7,13,1,14,2,4,2,22,7,7,21,4,16,23,11,17,7,16,7,0,23,26,35,23,31,16,34,19,21,43,34,40,42,2}

    Returns: 26

  57. {0,1,2,2,4,2,6,5,4,9,7,7,12,10,5,15,10,14,8,4,8,20,1,23,3,9,4,26,7,18,5,30,12,23,14,16,4,27,26,11,19,22,9,12,26,45,5,32,40,21}

    Returns: 23

  58. {0,1,1,3,2,2,4,1,8,4,4,7,6,5,5,2,9,12,18,5,15,12,19,9,8,15,14,13,26,1,6,31,16,18,7,26,7,22,4,5,30,16,11,36,7,17,12,35,41,3}

    Returns: 25

  59. {0,0,1,2,3,4,6,6,5,5,10,5,0,11,14,2,1,10,16,3,5,13,13,19,2,0,17,22,27,0,22,5,8,28,17,23,1,18,32,31,35,0,3,29,18,17,18,16,24,29}

    Returns: 26

  60. {0,0,0,0,4,1,1,0,1,4,8,0,12,10,12,15,4,5,2,3,17,19,4,13,18,7,18,26,0,18,27,19,17,29,18,9,32,4,24,16,37,25,22,9,0,2,10,33,2,47}

    Returns: 24

  61. {0}

    Returns: 1

  62. {0, 1}

    Returns: 1

  63. {0, 1, 2}

    Returns: 1

  64. {0, 0, 2, 3}

    Returns: 2

  65. {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}

    Returns: 1

  66. {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

  67. { }

    Returns: 1

  68. {0, 0, 1, 1, 2, 2 }

    Returns: 4

  69. {0 }

    Returns: 1

  70. {0, 0, 0 }

    Returns: 3

  71. {0, 0, 0, 0, 0, 0 }

    Returns: 6

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.
This problem was used for: