Statistics

Problem Statement for "MapleTreeEasy"

Problem Statement

Kaede loves maple trees. One day, she found a big maple tree and she described it as an undirected connected graph with N nodes and N-1 edges.

You are given the description in the int[] p. For each valid i, the i-th edge of the tree connects node p[i] and node i+1.


There are 2N-1 ways to choose a non-empty subset of nodes. Once we choose a subset of nodes, there is always a unique minimal subtree which contains all nodes in the subset.


Kaede got interested in thin subsets of nodes. A non-empty subset of nodes is called thin if the corresponding minimal subtree contains no nodes of degree 3 or more.


Please help Kaede: calculate and return the exact number of thin subsets of nodes for the given tree.

Definition

Class:
MapleTreeEasy
Method:
count
Parameters:
int[]
Returns:
long
Method signature:
long count(int[] p)
(be sure your method is public)

Notes

  • A subtree is any subgraph that is itself a tree.
  • The minimal subtree (among all subtrees that contain the chosen subset of nodes) is the unique subtree with the smallest number of nodes.

Constraints

  • N will be between 2 and 50, inclusive.
  • p will contain exactly N-1 elements.
  • For each valid i, p[i] will be between 0 and i, inclusive.

Examples

  1. {0, 1, 2, 3}

    Returns: 31

    This tree looks as follows: 0 \ 1 \ 2 \ 3 \ 4 Clearly, any non-empty subset of its nodes is thin.

  2. {0, 1, 0, 3}

    Returns: 31

    This tree looks as follows: 0 / \ 1 3 / \ 2 4 It is essentially the same tree as in the previous example, the only difference is that now we chose its middle node as the root. The answer is still the same: each non-empty subset of its nodes is thin.

  3. {0, 0, 0, 0, 0, 0}

    Returns: 43

    There are the following thin subsets of nodes: 1: Only the root (node 0) and nothing else. 6: The root and one of the leaves. 15: The root and two of the leaves. 6: One of the leaves. 15: Two of the leaves. That is a total of 43 thin subsets. No other subset is thin. As soon as we select at least three distinct leaves, the minimal subtree containing the selected nodes will contain node 0 and edges from this node to all selected leaves. Thus, in the minimal subtree there will be a node of degree at least 3.

  4. {0,0,0,0,3,4,6,7,4,5,2,8,5,9,14,14,13,0,16,8,5,2,19,6,6,17,18,16,9,16,6,25,11,12,0,21,0,13,15,24,28,7,19,38,31,16,29,39}

    Returns: 81999

  5. {0,0,0,3,3,2,6,7,1,6,1,11,12,6,0,15,16,7,8,8,7,18,18,9,10,2,6,21,17,20,29,27,21,15,4,23,21,33,30,6,24,31,3,28,21,29,44}

    Returns: 120961

  6. {0,0,0,1,4,0,0,6,8,2,0,1,10,12,10,13,10,17,2,3,8,7,2,19,5,0,15,5,24,15,17,7,11,13,16,15,33,18,27,30,13,7,42,28,1,18,32}

    Returns: 36897

  7. {0,0,2,3,1,0,5,5,2,2,9,0,4,11,4,12,9,14,11,6,9,17,17,11,23,18,7,27,17,17,20,5,10,15,6,11,18,0,33,10,23,17,29,32,26,18,37,8,6}

    Returns: 77695

  8. {0,1,0,2,0,5,4,2,3,7,9,0,0,12,0,7,2,10,3,6,7,19,21,5,1,25,25,8,25,4,25,24,10,15,30,17,17,15,18,23,39,22,28,0,38,26,21}

    Returns: 65521

  9. {0,0,2,3,4,0,1,7,0,4,3,8,1,2,4,0,14,14,15,9,8,8,16,19,8,4,20,3,21,21,21,30,17,10,5,17,21,1,15,29,27,29,35,14,5,1,43,44,11}

    Returns: 150673

  10. {0,1,1,0,4,5,2,2,1,7,1,8,6,6,5,6,10,16,2,8,18,18,7,0,3,17,12,19,26,18,8,30,2,4,20,25,3,21,38,21,12,19,11,6,24,16,39,30}

    Returns: 440203

  11. {0,1,1,1,2,2,4,0,6,6,10,7,0,11,14,3,10,5,13,7,19,6,2,20,9,13,1,0,3,11,30,29,5,23,10,15,7,19,16,27,18,6,32,22,38}

    Returns: 55665

  12. {0,1,2,0,4,2,4,5,6,1,2,11,9,8,3,11,8,6,11,1,20,7,7,10,17,4,25,6,6,27,5,17,4,21,20,27,16,33,6,11,36,18,19,0,16,19}

    Returns: 166441

  13. {0,1,0,0,1,3,4,2,4,2,6,10,10,0,6,1,3,0,2,2,1,9,18,19,5,1,7,26,2,11,1,7,20,8,8,35,22,36,20,22,2,19,34,24,0,23,22}

    Returns: 33241

  14. {0,1,1,0,0,4,6,0,3,0,3,9,1,1,10,6,2,5,1,1,4,6,1,4,14,18,23,6,17,2,2,5,22,10,23,0,10,11,30,30,6,13,27,41}

    Returns: 16131

  15. {0,1,0,3,0,3,6,4,7,1,6,3,6,9,13,9,15,8,5,5,20,3,1,1,17,10,6,1,8,14,17,15,22,5,31,4,7,12,14,25,0,24,38,26,44}

    Returns: 59689

  16. {0,1,2,1,3,1,2,0,4,4,7,6,5,11,14,9,0,2,6,14,8,8,20,9,11,1,10,14,12,13,20,25,11,29,0,3,29,18,34,21,16,25,33,29,20,40,19}

    Returns: 77023

  17. {0,1,1,2,2,1,6,5,3,9,3,11,3,12,11,6,15,9,16,11,14,8,10,15,20,7,26,26,13,17,14,5,1,14,31,26,0,19,35,18,5,13,7,40}

    Returns: 51057

  18. {0,0,1,1,3,1,4,6,3,5,4,4,11,7,1,8,10,17,5,9,17,16,3,21,18,14,21,14,1,22,28,14,6,24,17,21,4,16,32,33,27,27,14,43}

    Returns: 129961

  19. {0,1,2,0,4,2,2,5,1,5,8,8,9,9,3,9,9,13,5,19,10,4,21,2,20,14,11,1,20,21,0,27,7,2,29,32,31,37,5,28,32,31,34,37,42}

    Returns: 76501

  20. {0,0,1,1,3,2,3,2,7,8,10,7,8,11,12,12,6,6,8,17,17,19,22,10,11,5,9,21,9,28,15,14,19,5,4,26,23,27,16,1,11,5,26,35,41}

    Returns: 159187

  21. {0,0,0,0,0,4,3,6,6,0,1,0,4,5,4,13,6,16,6,7,6,9,20,16,7,4,20,15,13,12,7,11,17,32,14,17,27,35,18,30,5,10,38,28}

    Returns: 32205

  22. {0,1,1,2,4,0,1,5,7,3,6,6,6,5,11,14,11,3,10,10,15,4,6,9,2,18,15,13,11,18,1,29,20,7,33,24,34,1,33,37,40,17,14,4,29,33}

    Returns: 74803

  23. {0,1,0,3,4,0,4,0,1,7,5,7,5,7,9,4,10,15,16,17,19,2,1,10,12,12,25,7,8,20,24,1,21,3,25,23,14,18,2,18,26,2,12,19,13}

    Returns: 78307

  24. {0,1,2,0,2,1,1,5,0,7,4,8,10,6,6,3,14,4,7,11,9,13,8,19,4,24,25,11,11,19,6,19,17,6,32,11,16,5,33,19,37,35,36,36}

    Returns: 47887

  25. {0,0,1,0,0,3,2,6,5,8,10,4,7,4,1,4,9,2,1,3,0,11,18,19,8,9,1,0,0,18,21,8,19,20,15,23,20,16,18,11,14,22,14,15,22,38,43,44,11}

    Returns: 110733

  26. {0,0,1,1,2,1,0,1,1,4,5,4,6,3,4,6,4,6,17,7,10,11,19,10,20,14,24,7,19,3,4,8,15,27,29,33,18,7,1,38,39,38,40,12}

    Returns: 29227

  27. {0,1,0,0,0,0,3,1,8,1,10,4,3,9,12,3,10,11,1,12,14,12,12,8,5,19,9,1,11,11,17,8,18,18,25,13,31,6,28,16,22,10,8,18,23,42}

    Returns: 29293

  28. {0,1,0,0,2,0,3,7,5,5,5,10,4,0,0,6,15,17,15,6,11,17,15,19,17,23,26,19,17,10,3,14,22,10,10,9,12,31,14,10,33,10,4,34,14,12,1,33}

    Returns: 65985

  29. {0,1,2,0,4,0,4,3,7,7,8,9,12,12,7,10,5,4,0,15,10,6,18,3,14,11,5,24,2,19,17,17,22,32,23,10,28,3,1,9,25,7,25,22}

    Returns: 106495

  30. {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,39,32}

    Returns: 282583078339323

  31. {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,33,17,28,28,29,31,35}

    Returns: 8888502982771

  32. {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,20,31,23,42,16}

    Returns: 43985497449261

  33. {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,20,26,16,9,34,32,2}

    Returns: 11066381388577

  34. {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,1}

    Returns: 844424930131969

  35. {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,11,11,43,24,20,20,42}

    Returns: 17626618224697

  36. {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,40}

    Returns: 565148976677373

  37. {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}

    Returns: 1125899906842623

  38. {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,13,2,27,18,16,7,23,7,8}

    Returns: 2792402380279

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

    Returns: 13327

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

    Returns: 5073

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

    Returns: 8553

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

    Returns: 12061

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

    Returns: 6987

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

    Returns: 9763

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

    Returns: 6609

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

    Returns: 6897

  47. {0,0,0,0,1,0,1,1,1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,1}

    Returns: 3553

  48. {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}

    Returns: 1125899906842623

  49. {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}

    Returns: 2451

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

    Returns: 49

    0 / \ 1 2 / \ \ 3 4 5

  51. {0, 0, 0, 0, 0, 0 }

    Returns: 43

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

    Returns: 49

  53. {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 }

    Returns: 562949953421311

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: