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
{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.{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.{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.{0, 0, 1, 1, 2}Returns: 49
0 / \ 1 2 / \ \ 3 4 5