TwoDistance | Topcoder Archive

Problem Statement

This problem has a non-standard time limit: 5 seconds.

You are given an undirected tree on N nodes numbered from 0 to N-1. Each node x has some value V[x]. These values are then used to compute the cost of each node. Your task is to find the sum of costs of all nodes in the tree.

The cost of a node x is defined as follows:

Let's say the set of nodes at distance 2 from node x is set S. The cost of this node is the minimum value of abs(V[a]-V[b]) where a and b belong to S and a != b. If size of set S is less than 2, then the cost of node x is 0.

You are given the int N, the int[]s edge and int[]s val, and the ints D, seed. Use the pseudocode below to generate the edges of the tree and the values of all its nodes.

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

V = val
for i = size(val) to N-1:
    V[i] = A[i]

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

for i = 1 to N-1:
    the tree contains an edge between i and E[i]

Definition

Class:: TwoDistance
Method:: findMinValue
Parameters:: int, int[], int[], int, int
Returns:: long
Method signature:: long findMinValue(int N, int[] edge, int[] val, int D, int seed)
(be sure your method is public)

Notes

The distance between two nodes is the number of edges in the shortest path between the two nodes.

Constraints

N will be between 3 and 200,000, inclusive.
The number of elements in edge will between 1 and min(N, 100), inclusive.
edge[0] will be equal to -1.
For i > 0, edge[i] will be between 0 and i-1, inclusive.
The number of elements in val will between 0 and min(N, 100), inclusive.
Each element of val will be between 0 and 2,147,483,647, inclusive.
D will be between 1 and N, inclusive.
seed will be between 0 and 2,147,483,647, inclusive.

Examples

```
3
```
```
{-1, 0, 1}
```
```
{}
```
```
3
```
```
2
```
```
Returns: 0
```
Here, we can see that no node will have greater than 1 nodes at a distance of 2. Hence answer is 0.
```
5
```
```
{-1}
```
```
{1, 2, 3, 4, 5}
```
```
3
```
```
4
```
```
Returns: 6
```
Here we will obtain E array as {-1, 0, 1, 2, 2} and hence the edges as 0-1, 1-2, 2-3, 2-4. For node 0, only node 2 is at a distance of 2, hence cost for node 0 is 0. For node 1, it has nodes 3 and 4 at a distance of 2, hence cost for node 1 is abs(V[3]-V[4]) = 1 For node 2, again cost is 0. For node 3, nodes 1 and 4 are at a distance 2, hence cost is abs(V[1]-V[4]) = 3. Similarly for node 4, cost is 2. Hence answer is 1 + 2 + 3 = 6.
```
8
```
```
{-1}
```
```
{}
```
```
7
```
```
670614018
```
```
Returns: 3498908364
```

{-1}

{}

589477399

Returns: 88111951

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.