TopCoder SRM 786 - 1000: TwoDistance

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 , 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[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.

Test cases

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.
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[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.
input
- N 8
- edge { -1 }
- val { }
- D 7
- seed 670614018
output
Returns 3498908364
input
- N 200000
- edge { -1 }
- val { }
- D 84
- seed 589477399
output
Returns 88111951