SubtreeSum
SRM 698 (Google) · 2016-08-27 · by cgy4ever
Problem Statement
All nonempty connected subgraphs of our tree are called its subtrees. The value of a subtree is the bitwise OR of the weights of its vertices. For example, a subtree that contains vertices with weights 1, 4, and 6 has the value (1 OR 4 OR 6) = 7.
You are given the description of the tree: the
Constraints
- n will be between 2 and 50, inclusive.
- p will contain exactly n-1 elements.
- For each i, 0 <= p[i] <= i.
- x will contain exactly n elements.
- Each element in x will be between 0 and 1,000,000,000, inclusive.
{0}
{1,2}
Returns: 6
This is a tree with two vertices and a single edge 0-1. This tree has three subtrees: A subtree that only contains the vertex 0. A subtree that only contains the vertex 1. A subtree that contains both vertices. The values of these three subtrees are 1, 2, and 3. Hence, the correct return value is 1+2+3 = 6.
{0,1}
{1,2,4}
Returns: 23
This tree has six subtrees. Their values are 1, 2, 4, 3, 6, and 7, respectively. The sum of these values is 23.
{0,0,0,0,0,0,0,0,0,0}
{1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}
Returns: 33999993
This tree has 1034 subtrees. Each of those subtrees has value 1,000,000. Hence, the sum of values of all subtrees is 1,034,000,000. We should return 1,034,000,000 modulo (10^9 + 7) = 33,999,993.
{0,0,1,0,2,2,3,0,0,2,1}
{4,5,6,7,0,8,9,5,1,2,3,6}
Returns: 6378
{0}
{0,0}
Returns: 0
Submissions are judged against all 82 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SubtreeSum with a public method int getSum(vector<int> p, vector<int> x) · 82 test cases · 2 s / 256 MB per case