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