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) |