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?

Input:

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.

Output:

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

Sample Input:

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

Sample Output:

2

Source:

Submit