루미 알고리즘

#1618플래티넘Dalarna

PO 2025 온라인 예선코딩출제 Theodor Beskow영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
18Each city is connected to at most 2 roads.
211p_i = 1 for all i.
39p_i ≤ 1 for all i.
412N ≤ 7, p_i ≤ 5 for all i.
514N ≤ 100, p_i ≤ 100 for all i.
615N ≤ 1000
731No 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

출처 표기

출처: Programmeringsolympiaden 2025년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.