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

Monk missing home
Tag(s):

Medium-Hard

Problem
Editorial
Analytics

Spending a good amount of time in the Digital World, Monk was really missing his home and wanted to exit this world as soon as possible. Unlike the entry in the Digital World, there is a big barrier while exiting. A big tree $$T$$ with $$N$$ nodes, works as a Gatekeeper for the exit gate. Each node of a tree $$T$$ has a value associated with it given as $$A_{1}, A_{2}...A_{N}$$.
In order to exit, $$T$$ asked Monk to process $$N-1$$ queries on itself.
In each query:
1) Monk will be given a edge number $$e$$.
2) Monk has to delete edge e from the tree $$T$$.
3) After deleting the edge, Monk has to print total number of unordered pairs (u, v) such that there exits path from u to v and the absolute difference, i.e | Au - Av | ≤ D.

Note: Once an edge is deleted, it will be deleted permanently.
Monk is really missing his home, please help him.

INPUT:
First line of input will consists of two integers N and D. Next line will consists of N integers $$A_{1}, A_{2}...A_{N}$$. 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 u to v and | Au - Av | ≤ D

CONSTRAINTS:
2 ≤ N ≤ 105
-106 ≤ Ai ≤ 106
2 ≤ N ≤ 105
0 ≤ D ≤ 10

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Checkpoint - II)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications