Connection Status:
Competition Arena > SubtreeSumHash

SubtreeSumHash

TCO17 Round 1B · 2017-03-31 · by cgy4ever

TCO17 Round 1B · 2017-03-31 · by cgy4ever · Dynamic Programming
Class Name: SubtreeSumHash
Return Type: int
Method Name: count
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

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.

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
4)
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
546876
Returns: 215468008

Submissions are judged against all 98 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SubtreeSumHash with a public method int count(vector<int> weight, vector<int> p, int x) · 98 test cases · 2 s / 256 MB per case

Submitting as anonymous