Bombing plan

Question

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?

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 wi ,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

Answer 1

http://blog.csdn.net/kaqiur/article/details/48036401