RTREE2 - Valid Path

Roger was having fun solving his problems until he found this one. As you know, an undirected connected graph with N nodes and N-1 edges is called a tree. You are given an integer 'K' and a tree consisting of 'N' nodes. Each node 'i' has a value a(i) associated with it.

We call a path 'P' of tree valid if following conditions are satisfied:

  • P has at least 2 nodes associated with it.
  • Max a(u) - Min a(u) >= K (u belongs to the nodes present in the choosen P).

Your task is to count the number of Valid Paths.

Input

The first line contains two space-separated integers N and K.

The second line contains N space-separated positive integers a(1), a(2), ..., a(n).

Then the next n - 1 line each contains a pair of integers u and v denoting that there is an edge between u and v.

Output

Print the number of Valid Paths.

Example

SAMPLE INPUT
3 1
1 2 3
1 2
2 3

SAMPLE OUTPUT
3

CONSTRAINTS

1 <= N <= 5000
1 <= u,v <= N
0 <= K <= 10^9
0 <=  ai <= 10^9

 

Like Trees? Try the problems: RTREE, RTREE3 as well


Added by:Rana Saha
Date:2015-01-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Own problem (Codecracker 2015)

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.