SubtreeSumHash | Topcoder Archive

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

```
{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.
```
{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.
```
{10}
```
```
{}
```
```
10
```
```
Returns: 999999937
```
The answer is 10^10 % (10^9+7).

{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)2024, Topcoder, Inc. All rights reserved.