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 ints edge and ints 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]
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.