ETSums | Topcoder Archive

Problem Statement

You are given a rooted tree on N nodes. The nodes are numbered from 0 to N-1 with node 0 being the root. Each node x has three associated values: its parent P[x], its cost C[x], and its timestamp T[x].

You are given the parents and the costs of all nodes. The timestamps correspond to the order in which a depth-first search discovers the nodes of the tree. Formally, the timestamps can be computed using the following pseudocode:

counter = 1
define dfs(current_id):
    T[ current_id ] = counter
    counter += 1
    for each child_id such that P[child_id] = current_id:
        dfs(child_id)

// note that the children of a node are always processed in increasing order of their IDs
// in order to compute all timestamps, call:
dfs(0)

For each node x we will now define a new number: it's ET value, denoted ET[x].

Let the nodes on the (unique) simple path from the root to x be the nodes 0 = v₀, v₁, v₂, ..., v_k = x. The value ET[x] is defined as follows:

ET[x] = sum_i C[v_i] * i^T[x]

The sum is over all valid indices i, that is, 0 <= i <= k. The symbol ^ denotes exponentiation (i to the power of T[x]).

Find and return the sum of ET-values of all nodes in the tree, modulo 10^9+7.

In order to keep the test data small, the input for this problem is given in the following form: You are given the int N, the int[]s parent and cost, and the ints D, seed, and MX. Use the following pseudocode to generate the arrays P and C:

A[0] = seed
for i = 1 to 2*N-1:
	A[i] = (A[i-1] * 1103515245 + 12345) modulo 2147483648

P = parent
for i = size(parent) to N-1:
    P[i] = (A[i] modulo min(i,D)) + i - min(i,D) 

C = cost
for i = size(cost) to N-1:
	C[i] = A[N+i] modulo MX

Definition

Class:: ETSums
Method:: findSumOfETSums
Parameters:: int, int[], int[], int, int, int
Returns:: int
Method signature:: int findSumOfETSums(int N, int[] parent, int[] cost, int D, int seed, int MX)
(be sure your method is public)

Notes

Be careful to avoid potential overflows.
The reference solution would correctly solve any case that matches the constraints. It does not depend on the properties of the pseudorandom generator.

Constraints

N will be between 1 and 200,000, inclusive.
The number of elements in parent will between 1 and min(N, 100), inclusive.
parent[0] will be equal to -1, representing the fact that node 0 has no parent.
For each i, parent[i] will be less than i.
Number of elements in cost will between 0 and min(N, 100), inclusive.
Each element of cost will be between 0 and MX-1, inclusive.
D will be between 1 and 200,000, inclusive.
seed will be between 0 and 2,147,483,647, inclusive.
MX will be between 1 and 1,000,000,000, inclusive.

Examples

```
4
```
```
{-1,0,1,2}
```
```
{4,3,3,4}
```
```
1
```
```
0
```
```
5
```
```
Returns: 405
```
This tree is a path 0 -> 1 -> 2 -> 3. All values of P and C are given. The values of T are {1,2,3,4}. The ET values look as follows: ET[0] = 4*0^1 = 0 ET[1] = 4*0^2 + 3*1^2 = 3 ET[2] = 4*0^3 + 3*1^3 + 3*2^3 = 27 ET[3] = 4*0^4 + 3*1^4 + 3*2^4 + 4*3^4 = 375 Therefore the sum of all ET values is 0 + 3 + 27 + 375 = 405.
```
5
```
```
{-1,0,0,1,3}
```
```
{5,0,3,2,3}
```
```
1
```
```
0
```
```
6
```
```
Returns: 294
```
The tree looks as follows: 0 / \ 1 2 / 3 / 4 Timestamps are T = {1, 2, 5, 3, 4}. ET values are as follows: ET[0] = 5*0^1 = 0 ET[1] = 5*0^2 + 0*1^2= 0 ET[2] = 5*0^5 + 3*1^5 = 3 ET[3] = 5*0^3 + 0*1^3 + 2*2^3 = 16 ET[4] = 5*0^4 + 0*1^4 + 2*2^4 + 3*3^4 = 275 Finally, the sum will be 0 + 0 + 3 + 16 + 275 = 294.
```
4
```
```
{-1,0,0,0}
```
```
{3,2,3,0}
```
```
1
```
```
0
```
```
4
```
```
Returns: 5
```
In this tree each node other than 0 is its child. The timestamps are T = {1,2,3,4} again, and the ET values are {0, 2, 3, 0}.
```
10
```
```
{-1}
```
```
{}
```
```
7
```
```
176
```
```
15
```
```
Returns: 2425
```

{-1,0,0,0}

{4,7}

1000000000

Returns: 412779665

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.