루미 알고리즘

#1610다이아Five Rats at Gustav's

PO 2025 훈련 캠프코딩출제 Emil Sandberg영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Gustav has bought a very fine cheese. On his way home, he was so busy admiring his cheese that he fell into a manhole. He now finds himself in a sewer system with N manholes numbered from 0 to N-1. There are a total of N-1 pipes connecting the manholes, and one can move between any pair of manholes by traveling through the pipes. Each pipe takes a certain number of seconds to pass through.

Gustav is located in manhole number 0, and in the manholes r_1, …, r_M, there are rats. Soon, night will fall, and when the night begins, the rats will move toward Gustav. If any rat reaches manhole 0 before dawn, which occurs T seconds after night begins, they will eat his cheese, and he will be very sad.

To prevent this, he has hacked into the city's sewer system and can close manholes. If he closes a manhole for 1 second, no rats can exit that manhole during that second. However, rats can still enter a closed manhole. Gustav wants to keep certain manholes closed during parts of the night so that no rat reaches him before T seconds have passed.

Each manhole has a value e_i, representing the energy required to keep the manhole closed for 1 second. To avoid anyone noticing that he has hacked the sewer system, he wants to use as little energy as possible. What is the minimum total energy he needs to use?

Input

The first line contains the integers N, M, T (1 ≤ M < N ≤ 2 · 10^5, 1 ≤ T ≤ 10^8), the number of manholes, the number of rats, and the number of seconds until dawn.

The next N-1 lines contain the integers a_i, b_i, t_i (0 ≤ a_i,b_i ≤ N-1, 1 ≤ t_i ≤ 10^8), indicating that there is a pipe between manhole a_i and manhole b_i, and the time required to move between them is t_i. It is guaranteed that one can travel between every pair of manholes using the pipes.

After that, a line follows with N-1 integers e_1, …, e_{N-1} (1 ≤ e_i ≤ 10^5), each e_i being the energy required to close manhole number i for one second. Note that Gustav's manhole is manhole 0, and e_0 is not a given. He can never benefit from closing this manhole since the rats will eat the cheese as soon as they enter it.

Then, a line follows with M integers r_1, …, r_M (1 ≤ r_i ≤ N-1), where r_i indicates that a rat starts in manhole r_i. Initially, there is at most one rat in each manhole.

Output

Print an integer: the minimum amount of energy required to prevent any rat from reaching Gustav before T seconds have passed.

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
16e_i = 1 for all i = 1, …, N-1.
25M = 1
310M ≤ 2
410N, T ≤ 100
523N ≤ 2000
615The distance between manhole 0 and any other manhole is at most 20 pipes.
731No additional constraints.

Explanation of Sample 1

To use the least amount of energy, Gustav should keep manhole number 1 closed during the second, third, and fourth seconds of the night. The rat starting in manhole 2 will travel between manholes 2 and 1 during the first second of the night and remain in manhole 1 for 3 seconds. The rat starting in manhole 3 will travel between manholes 3 and 1 during the first two seconds and will be trapped in manhole 1 for the next two seconds. In the fifth second, both rats will move between manholes 1 and 0. Thus, both arrive at Gustav after exactly 5 seconds and do not get to eat his cheese. The answer is therefore 9.

Explanation of Sample 2

In this testcase, the best strategy is to keep manhole 2 closed during the first second. The rat starting in manhole 2 is trapped there during the first second, then moves between manholes 2 and 1 during the second second and between manholes 1 and 0 during the third second. The rat starting in manhole 3 travels between manholes 3 and 1 for all three seconds. The answer is therefore 3.

예제

예제 1

입력
4 2 5
0 1 1
1 2 1
1 3 2
3 5 5
2 3
출력
9

예제 2

입력
4 2 3
0 1 1
1 2 1
1 3 4
5 3 3
2 3
출력
3

출처 표기

출처: 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.