JOIN
Get Time

   Problem Statement  

 Problem Statement for TreeDistance

Problem Statement

    Cat Snuke has a tree with N vertices. The vertices are labeled 0 through N-1.



Snuke is able to modify the tree by performing a special operation. The operation consists of two steps. In the first step, he selects and removes an arbitrary edge of the tree. This divides the tree into two connected components. In the second step, he adds an arbitrary edge that connects those two components back into one tree.



You are given a int[] p that describes a tree, and an int K. The int[] p contains N-1 elements. For each i, the vertex p[i] and the vertex (i+1) are connected by an edge. Note that the initial labeling of the tree is such that for each i, p[i] is less than (i+1).



Snuke currently has the tree described by p. He may now modify it by repeatedly performing the operation described above. The number of operations Snuke will perform will be between 0 and K, inclusive.



Two trees are considered different if there are vertices p and q such that one of the trees contains the edge p-q but the other one does not. Return the number of different trees Snuke can produce, modulo 1,000,000,007.
 

Definition

    
Class:TreeDistance
Method:countTrees
Parameters:int[], int
Returns:int
Method signature:int countTrees(int[] p, int K)
(be sure your method is public)
    
 

Constraints

-p will contain between 1 and 49 elements, inclusive. (This means that N will be between 2 and 50, inclusive.)
-For each valid i, p[i] will be between 0 and i, inclusive.
-K will be between 0 and 50, inclusive.
 

Examples

0)
    
{0, 0}
1
Returns: 3
There are three different trees for N=3. The one described by this p contains the edges 0-1 and 0-2. Snuke can turn it into either of the other two trees in a single operation.
1)
    
{0, 1, 2, 2, 0}
1
Returns: 28
Some of the trees for N=6 cannot be obtained from the given one in a single operation.
2)
    
{0, 1, 2, 2, 0}
2
Returns: 222
In two operations Snuke can produce some more trees, but not all of them. For example, Snuke would need three operations to produce the tree with the edges 0-1, 0-2, 0-3, 0-4, and 0-5.
3)
    
{0, 1, 2, 2, 0}
50
Returns: 1296
In 50 operations Snuke can produce all trees.
4)
    
{0, 1, 2, 2, 0}
0
Returns: 1
As no modifications are allowed, there is only one tree Snuke can produce in this test case.
5)
    
{0, 1, 0, 3, 3, 4, 4, 5, 6, 8, 3, 1, 12, 12, 13, 10, 4, 8, 13, 17, 2, 10, 12, 20, 2, 14, 17, 19, 15, 0, 22, 15, 3, 8, 3, 17, 27, 2, 12, 38, 37, 4, 40, 29, 9, 22, 43, 32, 37}
1
Returns: 7124
6)
    
{0, 0, 0, 0, 2, 3, 1, 2, 3, 7, 3, 10, 8, 8, 9, 1, 2, 0, 7, 17, 19, 2, 17, 2, 0,
6, 4, 9, 12, 14, 8, 12, 10, 30, 20, 30, 8, 36, 28, 22, 8, 2, 2, 13, 26, 14, 46, 6, 25}
10
Returns: 310259667

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2014 TCO Algorithm Round 3B - Division I, Level Three
       2014 TCO Algorithm Parallel Round 3B - Division I, Level Three