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
Definition
- Class:
- SubtreesCounting
- Method:
- sumOfSizes
- Parameters:
- int, int, int, int, int
- Returns:
- int
- Method signature:
- int sumOfSizes(int n, int a0, int b, int c, int m)
- (be sure your method is public)
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.
Examples
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.
6864
287416172
93615980
825660639
437272514
Returns: 495877516
34938
115642242
900336294
967654924
939336996
Returns: 549379844
5001
407081653
575742560
603785123
356694563
Returns: 359045993
44670
914921043
55728979
171436198
145016844
Returns: 940834419
100000
362083631
602328371
358411147
753433677
Returns: 575184983
100000
263242147
175854056
1793741
972708694
Returns: 377880319
100000
468447560
830633775
94074272
943422141
Returns: 53509273
100000
641667536
405439309
75029819
7081372
Returns: 725789797
100000
0
1
1
1000000000
Returns: 665533303
100000
1
1
1
1000000000
Returns: 239924528
100000
0
1
1
10000
Returns: 194537463
100000
0
1
1
33333
Returns: 475359095
100000
129029
1000000000
100
100
Returns: 239924528
100000
999999999
999999999
999999999
999999999
Returns: 239924528
99997
13
12
0
100123123
Returns: 420036178
100000
0
0
0
100000000
Returns: 239924528
100000
15
1
0
10000000
Returns: 619801666
100000
1
0
1
100000
Returns: 239924528
100000
1000000000
1000000000
1000000000
1000000000
Returns: 239924528
5000
1000000000
1000000000
1000000000
3
Returns: 749439302