SubtreesCounting | Topcoder Archive

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 int n: the size of tree T. You are also given parameters for a pseudorandom generator: ints a0, b, c, and m. Use the pseudocode given below to generate the tree T. Watch out for integer overflow.

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.

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.