JOIN
Get Time

   Problem Statement  

 Problem Statement for SubtreeSumHash

Problem Statement

    You are given a tree T with n nodes. The nodes are numbered 0 through n-1. Each node of the tree has a positive integer weight. You are given the weights in the int[] weight with n elements. You are also given a int[] p with n-1 elements that describes the edges of the tree: for each valid i, there is an undirected edge between nodes (i+1) and p[i]. The constraints ensure that this will produce a valid tree.



A subtree of T is any subgraph of T that is a tree. The weight of a subtree is the sum of the weights of its vertices. Let S be the multiset that contains the weights of all nonempty subtrees of T. (In other words, for each subtree of T we calculate its total weight and add the result to S. Note that S may contain some duplicates.)



You are also given an int x. This value is used to define the hash of the multiset S: Hash(S) is defined as the sum of x^s over all elements s of S. For example, if S = {2, 3, 3} then Hash(S) = x^2 + x^3 + x^3.



Please calculate and return the value Hash(S) modulo 1,000,000,007.
 

Definition

    
Class:SubtreeSumHash
Method:count
Parameters:int[], int[], int
Returns:int
Method signature:int count(int[] weight, int[] p, int x)
(be sure your method is public)
    
 

Constraints

-weight will contain between 1 and 50 elements, inclusive.
-Each element in weight will be between 1 and 1,000,000,000, inclusive.
-p will contain exactly |weight|-1 elements.
-For each i, 0 <= p[i] <= i.
-x will be between 1 and 1,000,000,000, inclusive.
 

Examples

0)
    
{1,2,3}
{0,1}
10
Returns: 1102110
The tree contains the edges 1-0 and 2-1, so it looks like this: 0 - 1 - 2.

This tree has 6 subtrees: {0}, {1}, {2}, {0,1}, {1,2}, and {0,1,2}. Their weights are 1, 2, 3, 3, 5, and 6, respectively. Hence, S = {1, 2, 3, 3, 5, 6} and Hash(S) = x^1 + x^2 + 2*x^3 + x^5 + x^6 = 10 + 100 + 2*1000 + 100000 + 1000000 = 1102110.
1)
    
{123456789,987654321,111111111,999999999}
{0,0,0}
1
Returns: 11
There are 11 subtrees. Their weights do not matter: as x = 1, Hash(S) is simply the number of subtrees.
2)
    
{10}
{}
10
Returns: 999999937
The answer is 10^10 % (10^9+7).
3)
    
{3,7,6,8,9,4,2,1,5,6,7,8,9,6,1,2,3,5}
{0,0,0,3,1,1,2,0,0,3,7,8,9,0,0,4,1}
987654321
Returns: 46327623

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:
       2017 TCO Algorithm Round 1B - Division I, Level Three