Limits 3s, 512 MB

You will be given a tree of N nodes. Each node has a given value and the distance between adjacent nodes is 1 unit. Now you have to find how many pair of nodes exists whose sum will be 0 and the distance between them will be less than L.

Input

Input starts with an integer N (1<N<=300000) denoting the number of nodes in the tree. The next line contain N space separated integers which represents the value of each node numbered from 1 to N respectively. Then there are N-1 lines, each containing two integers: u v (1<=u, v<=N, u≠v) meaning that there is an edge between u and v.
Next line contain an integer L (1<=L<=N)
Value of each node will fit into signed integer (-2147483648 to 2147483647).

Output

For each test case print the result in a single line.

Samples

InputOutput
5
1 1 -1 1 -1
1 2
1 3
2 4
3 5
4
5
InputOutput
2
0 -2
1 2
2
1

For the first sample there are 6 pairs node whose sum is 0 and they are (1,3), (1,5), (2,3), (2,5), (4,3), (4,5).
(4, 5) is invalid because the distance between them is 4 (>=L).

For second sample the only valid pair is (1,1).

Submit

Login to submit.

Statistics

67% Solution Ratio
nahid08Earliest, Oct '20
nusuBotFastest, 0.9s
nusuBotLightest, 78 MB
nahid08Shortest, 3551B
Toph uses cookies. By continuing you agree to our Cookie Policy.