Bombing plan

Time Limit: 4000 ms Memory Limit: 65536 KiB

Problem Description

Kingdom Y is in the war with kingdom X. Kingdom X consists of N cities,there are N-1 bidirectional roads which are all 1 long ,each of them connect a pair of cities,the N cities are all connect by the N-1 bidirectional.People can travel through the roads.

Now kingdom Y is going to bomb kingdom X. Every city of kingdom X has its own value W. If city i was to be bombed, then all the cities that lie within the distance W(i) from city i would be destroyed as well. The king of kingdom Y wants to know the minimum bombing time that can destroy all the cities in kingdom X. Could you help him?


There are multiple test cases. Please process till EOF.
In each test case: 
First line: an integer n(n<=10^5) indicating the number of city
Second line:contain n numbers w[i](0<=w[i]<=100) ,indicating that the value of city[i],
Next n - 1 lines: each contains two numbers ui and vi, (1 ≤ ui,vi<=n), indicates that there’s one road connecting city ui and vi.


For each case,output one number, denotes the minimum number of bombing times.

Sample Input

1 1 1 1 1
1 2
2 3
3 4
4 5

Sample Output





2015 Multi-University Training Contest 1