# SRM 78611000TwoDistance

## 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 = 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 , vector<int> , vector<int> , int , int
• Returns long long
• Method signature long long findMinValue(int N, vector<int> edge, vector<int> val, int D, int seed)
(be sure your method is public)

## Limits

• Time limit (s) 5.000
• Memory limit (MB) 256

## 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 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.

## Test cases

1. input
• N 3
• edge { -1, 0, 1 }
• val { }
• D 3
• seed 2
output
Returns 0
note
Here, we can see that no node will have greater than 1 nodes at a distance of 2. Hence answer is 0.
2. input
• N 5
• edge { -1 }
• val { 1, 2, 3, 4, 5 }
• D 3
• seed 4
output
Returns 6
note
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-V) = 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-V) = 3. Similarly for node 4, cost is 2.

Hence answer is 1 + 2 + 3 = 6.
3. input
• N 8
• edge { -1 }
• val { }
• D 7
• seed 670614018
output
Returns 3498908364
4. input
• N 200000
• edge { -1 }
• val { }
• D 84
• seed 589477399
output
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)2003, TopCoder, Inc. All rights reserved.