All Tracks Data Structures Disjoint Data Structures Basics of Disjoint Data Structures Problem

Final Problem
/
No tags
Problem
Editorial
Analytics

Sumit has successfully completed all the preliminary rounds of CodoHolic event in Aurora 2K18. Now, to win this event he has to solve the final problem which is prepared by one of the famous coder Himanshu. The final problem is as follows:

Given a tree with 'N' nodes and each node has some cost associated with it given by Ai. Now, sumit has to perform N-1 queries on this tree in such a manner that in each querry :

  • Sumit has to permanently delete edge e from the tree.
  • After deleting the edge e, Sumit has to count and print the total no. of unordered pairs (u, v) such that there exits a path from node u to node v and the absolute difference, i.e | Au - Av | ≤ D.

Input :

  • First line of input will consists of two integers N and D.
  • Next line will consists of N space separated integers A1,A2,A3...AN.
  • Next N-1 lines will consists of two integers u and v. It denotes that ith edge consists of two nodes u and v.
  • Next N-1 lines will consists of one integer e denoting the queries.

Output :

  • For each query, print the total number of unordered pairs (u, v) such that there exits path from node u to node v and | Au - Av | ≤ D.

Constraints :

  • 2<=N<=105
  • -106<=Ai<=106
  • 0<=D<=106
SAMPLE INPUT
5 5
3 -2 -1 -4 0 
5 3
4 3
1 4
2 4
4
1
2
3
SAMPLE OUTPUT
5
2
0
0
Explanation

If we remove edge 4, all the required (u,v) pairs are (1,3), (1,5) , (3,4) , (3,5) , (4,5).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?