영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
Harry loves Dalarna and dreams of making it Sweden's top-ranked county. After thorough analysis, he has determined that if every city i in Dalarna had p_i more car trips passing through, Dalarna would secure first place. To achieve this, Harry plans to order taxis to drive between the cities, with each taxi traveling along the shortest path between two cities.
Dalarna's road network consists of N cities and N-1 roads. Each road directly connects two cities. If a taxi is in a city, it can travel to all cities that are directly connected to it via a road. Furthermore, the network is constructed so that it is always possible to travel between any pair of cities using one or more roads.
For each city i, Harry needs to ensure that at least p_i taxis pass through the city to meet his goal. A taxi travels between two specified cities in the network and follows the shortest path.
To avoid raising suspicion, Harry wants to use as few taxis as possible. Help him calculate the minimum number of taxis he needs to order to meet the requirements.
Input
The first line contains an integer N (1 ≤ N ≤ 10^5), the number of cities in Dalarna.
The second line contains N integers p_1, p_2, ..., p_N (0 ≤ p_i ≤ 10^9), where p_i indicates the number of taxis that must pass through city i.
The next N-1 lines describe the roads between the cities. Each line contains two integers u and v (1 ≤ u, v ≤ N), indicating that there is a road between city u and city v. The road network connects all cities.
Output
Print a single integer: the minimum number of taxis Harry needs to order.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 8 | Each city is connected to at most 2 roads. |
| 2 | 11 | p_i = 1 for all i. |
| 3 | 9 | p_i ≤ 1 for all i. |
| 4 | 12 | N ≤ 7, p_i ≤ 5 for all i. |
| 5 | 14 | N ≤ 100, p_i ≤ 100 for all i. |
| 6 | 15 | N ≤ 1000 |
| 7 | 31 | No additional constraints. |
(그림은 원문 저장소에서 볼 수 있습니다)
Figure 1: The road network for the 6 cities in sample 3.
(그림은 원문 저장소에서 볼 수 있습니다)
Figure 2: A possible solution for sample 3, where the blue, orange, purple, green, and red paths represent 5 different taxi routes.
예제
예제 1
3 3 1 5 1 2 2 3
5
예제 2
4 1 2 2 2 1 3 4 2 3 2
2
예제 3
6 1 4 2 1 2 2 2 1 3 1 4 1 5 4 6 4
5