Dostavljač
레이팅 미적용의견: 0
2 \(s / 64\) \(MB / 140\) points
Ever since Krešo started growing chili peppers, \(N\) restaurants all over Croatia showed
interest in his peppers so they could enrich their dishes with real spice. Because of high
demand, Krešo decided to start working as a delivery guy of chili peppers.
The restaurants are denoted with numbers from 1 to \(N\) and are mutually connected with \(N\) -
1 roads such that traveling between any two restaurants is possible. Krešo begins his
journey in the restaurant denoted with 1. In one unit of time, he can either drive to the
adjacent restaurant or deliver the peppers to the current restaurant. For each restaurant, we
know the required amount of peppers \(A\) {i}{ }.
Since delivering goods is tiring, Krešo decided to spend a total of \(M\) units of time on delivery
and travel, after which he plans to take a break.
Determine the maximal amount of peppers Krešo can deliver in the given timeframe. You
can assume that Krešo always carries an unlimited supply of peppers.
The first line of input contains two integers \(N\) and \(M\) (1 ≤ \(N\) , \(M \le 500\)), the number of
restaurants and the time Krešo plans to spend delivering peppers.
The second line of input contains \(N\) integers \(A\) {i} (1 ≤ \(A\) ≤10 {6}{ }), the required amount of peppers
for restaurants denoted with \(i\) (1 ≤ \(i\) ≤ \(N\) ).
Each of the following \(N - 1\) lines contains two integers \(U\) and \(V\) (1 ≤ \(U\) , \(V\) ≤ \(N\) , \(U\) ≠ \(V\) ) that
represent the road between restaurants \(U\) and \(V\) .
You must output the maximal amount of peppers Krešo can deliver in the given timeframe.
3 5
9 2 5
1 2
1 3
4 5
1 1 1 2
1 2
2 3
3 4
5 10
1 3 5 2 4
5 2
3 1
2 3
4 2output
output
14
3
15
2 s / 64 MB / 140 pointsClarification of the first test case:
In the first step, Krešo will deliver the peppers to restaurant 1.
In the second step, Krešo will travel to restaurant 3.
In the third step, Krešo will deliver the peppers to restaurant 3.
He is left with 2 units of time, in which he can drive to restaurant 2, but he lacks one unit of time to
deliver the peppers to that restaurant.
평가 및 의견
Dostavljač
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Dostavljač