SubtreesCounting
SRM 683 · 2016-01-04 · by Arterm
Problem Statement
You are given an undirected tree T. (The input format is specified below.) The vertices of the tree are numbered 0 through n-1.
A subtree of T is any subgraph of T that is connected. The size of a subtree is the number of vertices it contains. Two subtrees are considered different if one of them contains a vertex the other doesn't.
Let X be the sum of sizes of all subtrees of T. As X can be large, compute and return the value (X modulo 1,000,000,007).
You are given the
a[0] = a0
for i = 1 .. n-2:
a[i] = (b * a[i-1] + c) mod m
for i = 1 .. n-1:
j = a[i-1] mod i
add an edge between vertices i and j
Constraints
- n will be between 1 and 10^5, inclusive.
- a0, b and c will be between 0 and 10^9, inclusive.
- m will be between 1 and 10^9, inclusive.
3 1 1 1 1 Returns: 10
Tree T has 3 vertices and contains the edges 0-1 and 0-2. This tree has six different subtrees. These correspond to the following sets of vertices: {0}, {1}, {2}, {0,1}, {0,2}, and {0,1,2}. The sizes of these subtrees are 1, 1, 1, 2, 2, and 3. Thus, the correct answer is 1+1+1+2+2+3 = 10.
5 1 2 3 100 Returns: 52
Tree T contains the edges 0-1, 1-2, 1-3, 1-4.
1 1 1 1 1 Returns: 1
Just one vertex in T.
2 5 6 7 8 Returns: 4
Tree T has 2 vertices and contains the only edge 0-1.
100000 123 46645 4564579 1000000000 Returns: 769840633
Watch out for integer overflow. First 10 elements (a[0], a[1], ..., a[9]) of the generated sequence are: 123, 10301914, 537343109, 373883884, 818333759, 182753134, 524500009, 307484384, 613656259, 765634.
Submissions are judged against all 25 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SubtreesCounting with a public method int sumOfSizes(int n, int a0, int b, int c, int m) · 25 test cases · 2 s / 256 MB per case