Bombing plan

Time Limit
5s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
20.00%(2/10)
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:

2015 Multi-University Training Contest 1


Submit