Statistics

Problem Statement for "WalkOverATree"

Problem Statement

Given is a tree on n nodes. The nodes are numbered 0 through n-1. You are given the description of the tree as a int[] parent with n-1 elements. For each valid i, there is an edge between vertices (i+1) and parent[i].

A person is currently standing in node 0. In a single step, the person can move from its current node to any adjacent node. You are given an int L. The person is allowed to make at most L steps.

Return the maximum number of nodes the person can visit during the walk. Node 0 (where the walk starts) and the node where the walk ends count as visited. Each visited node is only counted once, even if it is visited multiple times.

Definition

Class:
WalkOverATree
Method:
maxNodesVisited
Parameters:
int[], int
Returns:
int
Method signature:
int maxNodesVisited(int[] parent, int L)
(be sure your method is public)

Constraints

  • parent will contain between 0 and 49 elements, inclusive.
  • For each i, parent[i] will be between 0 and i, inclusive.
  • L will be between 1 and 100, inclusive.

Examples

  1. {0, 0}

    2

    Returns: 2

    The tree consists of edges 1-0 and 2-0. Our person will start in node 0 and can make at most L=2 steps. In two steps, the best we can do is visit one of the nodes 1 and 2.

  2. {0, 0}

    3

    Returns: 3

    This is the same tree, only now we have L=3. In three steps the person can visit all three nodes: for example, by going from node 0 to node 1, back to node 0, and finally to node 2. Note that even though the person visited node 0 twice, we only count it once.

  3. {0, 1, 2, 3}

    2

    Returns: 3

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

    1

    Returns: 2

  5. {0,0,1,2,3,2,3,1,3,0,1,8,6,8,0,5,15,0,9}

    4

    Returns: 5

  6. {0,0,0,1,1,3,5,1,4,5,2,2,10,5,10,10,11,13,8,3,18,15,20,20,23,8,11,26,4}

    26

    Returns: 17

  7. {0, 0, 2, 0}

    100

    Returns: 5

    As the tree is very small and L large, the person can easily visit all nodes.

  8. {}

    1

    Returns: 1

  9. {}

    73

    Returns: 1

  10. {}

    58

    Returns: 1

  11. {0}

    1

    Returns: 2

  12. {0}

    2

    Returns: 2

  13. {0}

    21

    Returns: 2

  14. {0}

    35

    Returns: 2

  15. {0,0}

    1

    Returns: 2

  16. {0,0}

    2

    Returns: 2

  17. {0,0}

    58

    Returns: 3

  18. {0,0}

    50

    Returns: 3

  19. {0,0,0}

    1

    Returns: 2

  20. {0,0,0}

    2

    Returns: 2

  21. {0,0,1}

    44

    Returns: 4

  22. {0,0,1}

    27

    Returns: 4

  23. {0,0,0,2}

    1

    Returns: 2

  24. {0,0,0,1}

    3

    Returns: 3

  25. {0,0,1,1}

    76

    Returns: 5

  26. {0,0,1,1}

    41

    Returns: 5

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

    1

    Returns: 2

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

    3

    Returns: 3

  29. {0,0,1,0,3}

    46

    Returns: 6

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

    61

    Returns: 6

  31. {0,0,1,1,0,3}

    1

    Returns: 2

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

    3

    Returns: 3

  33. {0,0,0,2,3,4}

    36

    Returns: 7

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

    19

    Returns: 7

  35. {0,0,1,1,3,4,3}

    1

    Returns: 2

  36. {0,0,1,1,0,3,4}

    4

    Returns: 4

  37. {0,0,1,0,0,1,0}

    12

    Returns: 8

  38. {0,0,0,1,0,2,3}

    46

    Returns: 8

  39. {0,0,1,2,2,3,5,6}

    2

    Returns: 3

  40. {0,0,1,0,1,1,1,1}

    3

    Returns: 3

  41. {0,0,1,1,3,4,4,5}

    83

    Returns: 9

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

    42

    Returns: 9

  43. {0,0,1,1,3,1,1,4,1}

    1

    Returns: 2

  44. {0,0,1,1,2,0,2,6,5}

    4

    Returns: 4

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

    82

    Returns: 10

  46. {0,0,1,1,0,0,2,2,7}

    52

    Returns: 10

  47. {0,0,1,2,1,2,5,1,2,1,2,1,3,12,7,10,12,16,14,11,14,12,19,16,13,8,19,22,12,23,1,24,29,9,1,1,13,32,28}

    3

    Returns: 4

  48. {0,0,1,0,3,2,4,3,3,3,9,3,9,4,0,13,13,10,13,9,8,10,14,10,5,6,19,20,10,20,26,9,29,7,4,30,14,33,37}

    7

    Returns: 7

  49. {0,0,0,2,1,2,4,5,6,8,9,1,1,3,9,5,11,6,10,17,15,9,9,6,5,1,5,5,5,9,22,28,4,21,28,17,26,36,24}

    12

    Returns: 10

  50. {0,0,0,0,2,1,5,2,2,4,1,10,0,9,10,6,9,14,0,17,7,9,19,16,22,15,8,7,15,1,19,13,1,31,14,7,25,3,31}

    29

    Returns: 18

  51. {0,0,1,0,1,3,5,5,2,4,3,3,10,5,12,8,12,15,8,11,11,14,7,0,6,5,22,10,5,10,18,16,22,16,1,12,19,7,36,38}

    4

    Returns: 5

  52. {0,0,0,2,1,4,4,6,0,0,4,8,3,11,2,2,12,14,10,2,10,11,15,4,4,24,4,13,3,26,5,3,31,19,15,12,14,28,27,22}

    7

    Returns: 7

  53. {0,0,1,0,2,4,3,5,7,8,7,4,2,1,13,5,4,5,16,9,5,9,20,14,20,10,16,24,24,27,24,13,0,31,25,18,34,30,10,19}

    65

    Returns: 37

  54. {0,0,0,0,1,0,5,6,4,7,0,9,10,6,13,9,14,1,5,0,14,6,13,6,7,1,6,13,22,27,20,6,0,7,22,13,32,19,6,12}

    93

    Returns: 41

  55. {0,0,0,1,0,3,0,2,1,2,3,8,10,8,4,14,12,9,9,8,10,4,8,4,2,13,25,17,4,14,24,30,9,28,29,22,12,18,23,31,34}

    4

    Returns: 5

  56. {0,0,0,2,0,3,2,6,0,1,6,5,7,1,0,12,2,16,15,10,11,20,0,1,17,23,13,14,8,10,18,5,28,15,13,5,12,24,3,3,36}

    6

    Returns: 6

  57. {0,0,0,0,1,1,4,2,2,0,1,5,4,4,8,10,12,3,13,11,17,2,1,13,2,18,21,22,11,5,2,25,25,13,25,15,20,20,34,38,3}

    30

    Returns: 19

  58. {0,0,0,0,1,0,3,2,6,4,2,8,11,0,5,9,3,10,7,7,1,9,6,22,3,3,23,18,12,3,13,27,29,28,17,0,25,14,33,8,23}

    17

    Returns: 12

  59. {0,0,1,1,0,3,3,1,2,8,8,8,1,6,11,1,14,11,3,9,8,16,12,3,1,21,17,21,12,3,8,14,21,26,0,20,24,33,28,18,19,6}

    4

    Returns: 5

  60. {0,0,0,0,2,1,2,5,1,4,8,5,2,0,3,8,7,16,17,13,10,12,12,5,15,22,3,2,14,24,17,15,4,22,4,3,18,5,7,35,37,15}

    8

    Returns: 8

  61. {0,0,0,1,3,4,5,5,6,1,6,6,1,2,7,0,10,7,9,3,2,1,19,0,15,8,10,16,2,14,12,11,21,6,4,27,15,19,15,15,35,23}

    99

    Returns: 43

  62. {0,0,1,0,0,0,2,3,5,6,5,7,11,10,11,6,5,6,13,15,14,11,13,6,16,16,11,19,0,4,26,0,0,16,13,21,33,2,20,26,6,23}

    88

    Returns: 43

  63. {0,0,1,0,1,4,0,5,1,1,4,6,7,11,0,6,3,9,6,4,13,10,2,0,0,15,15,16,12,28,11,16,16,9,2,30,21,26,21,11,7,40,21}

    4

    Returns: 5

  64. {0,0,0,0,2,0,2,4,0,0,8,6,6,8,5,11,3,10,15,3,1,18,13,6,14,15,8,15,8,7,5,21,27,29,6,22,8,4,22,15,15,12,32}

    5

    Returns: 5

  65. {0,0,0,0,3,4,0,6,0,8,3,3,8,12,11,11,0,3,12,14,8,1,7,17,7,3,9,19,13,23,1,1,17,5,12,15,3,2,25,35,1,19,17}

    24

    Returns: 15

  66. {0,0,1,0,1,4,5,5,4,8,3,6,2,6,0,5,3,8,14,8,14,3,10,7,23,1,3,3,21,15,29,21,22,11,7,10,11,2,19,19,24,34,35}

    41

    Returns: 24

  67. {0,0,1,2,0,3,4,5,4,0,3,6,1,7,4,7,14,3,0,12,6,15,21,22,15,14,21,7,1,13,22,23,13,11,7,4,29,5,16,3,3,5,25,6}

    3

    Returns: 4

  68. {0,0,0,2,2,4,3,1,0,8,3,3,3,11,7,13,3,16,2,6,1,9,19,2,7,3,23,21,8,2,13,0,28,20,28,0,32,26,27,1,16,8,24,30}

    6

    Returns: 6

  69. {0,0,0,1,0,0,3,5,6,8,7,9,1,10,1,2,15,6,8,11,14,17,8,14,3,21,23,3,21,15,12,5,21,31,11,13,7,17,20,26,28,16,36,26}

    73

    Returns: 41

  70. {0,0,0,1,3,0,0,2,0,3,9,9,4,5,1,14,0,14,15,13,18,14,4,15,9,16,9,12,10,17,21,24,22,5,13,3,7,8,8,11,6,28,5,2}

    80

    Returns: 44

  71. {0,0,1,1,1,3,1,1,1,2,3,9,7,11,4,2,12,4,11,11,10,7,16,21,0,9,21,22,2,4,20,13,30,15,1,20,9,27,32,24,34,1,15,35,3}

    1

    Returns: 2

  72. {0,0,1,2,3,2,3,0,0,4,7,3,7,4,4,13,0,10,16,2,15,8,3,14,6,9,10,11,3,24,1,2,7,2,31,4,26,31,9,11,5,40,28,34,23}

    7

    Returns: 7

  73. {0,0,0,0,1,4,0,3,2,5,3,3,8,10,7,10,9,3,13,0,5,9,3,19,3,6,14,8,10,24,5,21,31,7,23,31,16,23,25,5,4,31,28,33,0}

    98

    Returns: 46

  74. {0,0,0,0,1,1,2,1,0,5,3,2,0,1,8,0,8,1,3,3,3,18,4,0,8,6,19,24,0,15,29,26,4,25,26,26,5,31,13,12,4,27,15,2,13}

    93

    Returns: 46

  75. {0,0,1,1,3,0,4,5,3,3,5,9,9,8,1,14,3,10,6,3,14,15,2,9,3,10,13,6,25,28,19,30,20,12,12,30,33,5,16,6,17,30,10,35,0,7}

    1

    Returns: 2

  76. {0,0,0,1,1,1,3,3,5,5,8,8,11,5,13,9,14,12,15,9,0,11,1,21,6,22,8,26,13,22,23,0,12,7,30,4,34,10,0,5,31,5,22,5,4,6}

    7

    Returns: 7

  77. {0,0,0,1,2,0,5,3,3,4,0,9,1,7,11,4,1,13,7,14,2,18,19,1,16,8,7,2,15,25,29,11,6,26,32,3,8,19,3,3,9,15,2,5,28,12}

    16

    Returns: 11

  78. {0,0,1,1,1,0,0,2,1,7,5,2,10,5,5,12,5,4,14,10,18,3,10,18,11,7,23,13,17,8,21,2,19,24,11,20,23,9,34,36,2,39,41,24,33,12}

    46

    Returns: 27

  79. {0,0,0,0,3,0,4,4,1,4,7,5,7,4,2,14,5,6,6,11,6,5,1,2,21,12,7,12,11,17,26,28,19,9,0,34,29,16,27,5,20,25,39,21,12,29,19}

    2

    Returns: 3

  80. {0,0,1,2,0,4,0,2,3,0,0,8,7,12,7,9,2,2,5,18,17,13,3,11,15,17,24,10,9,1,19,15,15,14,3,8,33,25,16,7,21,22,14,38,29,6,36}

    6

    Returns: 6

  81. {0,0,1,2,2,2,0,0,6,8,8,2,3,9,11,7,8,2,14,2,11,4,2,20,8,17,4,22,13,19,10,3,24,29,20,7,15,28,35,36,5,0,10,11,17,17,36}

    82

    Returns: 45

  82. {0,0,1,0,1,2,5,6,0,4,3,10,0,6,3,8,4,16,5,15,15,1,20,1,2,6,24,18,21,28,27,19,0,16,4,17,12,13,34,30,23,31,26,38,39,33,34}

    82

    Returns: 46

  83. {0,0,1,2,0,0,2,4,4,6,1,3,1,4,10,7,9,1,0,16,14,5,17,7,17,24,24,13,8,14,9,10,15,19,21,29,23,33,29,21,34,9,10,27,30,29,35,10}

    1

    Returns: 2

  84. {0,0,1,2,1,4,3,0,0,1,4,0,5,2,10,2,10,3,3,15,3,9,5,17,13,15,15,21,25,7,21,12,20,6,25,17,22,20,22,5,20,34,1,19,40,26,14,22}

    6

    Returns: 6

  85. {0,0,1,1,0,3,5,3,5,5,0,0,10,4,7,4,11,9,0,11,11,1,1,14,6,8,3,8,24,16,4,24,1,5,18,13,2,1,34,31,37,39,1,4,14,22,37,44}

    21

    Returns: 14

  86. {0,0,0,1,3,0,5,2,4,1,8,10,8,11,9,11,13,16,13,5,11,18,5,4,11,6,14,22,5,22,12,27,0,23,22,10,15,36,15,19,38,8,31,21,25,9,42,20}

    52

    Returns: 30

  87. {0,0,1,0,2,1,2,6,5,1,6,3,2,0,2,1,5,0,7,5,18,4,9,2,6,15,23,5,0,21,21,23,11,7,4,32,17,15,12,26,12,30,18,18,39,13,12,1,3}

    3

    Returns: 4

  88. {0,0,1,1,2,2,4,3,1,8,0,2,2,5,13,9,10,14,17,16,16,0,8,7,19,20,16,11,19,15,15,26,12,16,10,13,22,19,30,14,25,39,5,15,8,29,44,0,47}

    9

    Returns: 9

  89. {0,0,0,1,2,2,4,6,2,0,2,3,1,11,6,1,12,0,7,2,11,9,11,8,5,16,4,25,3,28,16,11,12,18,32,9,17,24,2,36,13,14,10,11,22,20,15,0,9}

    63

    Returns: 35

  90. {0,0,0,0,2,3,3,6,4,5,4,9,1,4,8,13,15,11,8,5,0,18,16,7,6,14,22,20,13,1,23,2,15,1,4,0,1,29,15,26,14,36,21,35,8,31,1,12,4}

    56

    Returns: 32

  91. {0, 0, 2}

    4

    Returns: 4

  92. {}

    1

    Returns: 1

  93. {0, 0, 0, 1, 1, 3, 5, 1, 4, 5, 2, 2, 10, 5, 10, 10, 11, 13, 8, 3, 18, 15, 20, 20, 23, 8, 11, 26, 4, 8, 0, 15, 7 }

    31

    Returns: 19

  94. { }

    1

    Returns: 1

  95. {0, 1, 0, 3, 4, 3, 4, 1, 0, 0, 6, 0, 1, 0, 0, 1, 8, 2, 7, 0, 16, 14, 0, 14, 16, 0, 3, 4, 11, 23, 0, 2, 11, 9, 7, 14, 3, 31, 1, 19, 20, 0, 1, 1, 1, 3, 1, 3, 0 }

    100

    Returns: 50

  96. {0, 0, 0, 1, 1, 3, 5, 1, 4, 5, 2, 2, 10, 5, 10, 10, 11, 13, 8, 3, 18, 15, 20, 20, 23, 8, 11, 26, 4 }

    100

    Returns: 30

  97. {0, 1, 2, 3, 0, 5, 6, 7 }

    100

    Returns: 9

  98. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    100

    Returns: 50

  99. { }

    100

    Returns: 1

  100. { }

    6

    Returns: 1

  101. {0, 1, 2, 3, 0 }

    8

    Returns: 6

  102. {0, 1, 0, 1, 4, 1, 5, 0, 4, 7 }

    14

    Returns: 10

  103. {0, 1, 1, 1, 1, 1, 0, 7, 8 }

    3

    Returns: 4

  104. {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22 }

    79

    Returns: 43

  105. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    95

    Returns: 49

  106. {0, 1, 2, 0, 4, 5, 6, 7 }

    9

    Returns: 8

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: