Problem C
Tree Advertisement
Languages
en
sv
In Azerbaijan there are $N$ cities, numbered between $1$ and $N$, connected by $N - 1$ roads in such a way that each pair of cities are connected by some sequence of roads. It’s soon time for this year’s International Olympiad in Informatics in the capital, Baku (city $1$), and everyone in the whole country will then drive from their hometown to the capital to watch the contest.
You want to use this opportunity to advertise your new, really clever online programming judge by putting up advertisement posters on a lot of trees along different roads. If you put up posters along a road, everyone who travels along that road during the trip from their hometown to the capital will see the poster.
You have determined that it doesn’t help if someone sees your posters more than once during their travels – your judge is so impressive that everyone wants to use it after seeing the poster just once! Each road has a certain cost for putting up a poster on all the trees along the road, each city has a given population, and you have a limited budget. If you put up the posters optimally, what’s the greatest number of people who will see at least one poster on their way to the capital?
Input
The first line contains two integers $N$ and $B$ ($1 \le N \le 2\, 000$, $1 \le B \le 30\, 000$), the number of cities and your budget in Swedish crowns.
The second line contains $N-1$ integers $p_2, p_3, \dots , p_ N$ ($0 \le p_ i \le 30\, 000$), where $p_ i$ is the population of the $i$’th city.
The following $N-1$ lines describe all the road in Azerbaijan. The $i$’th of these contains the integers $a_ i, b_ i$ ($1 \le a_ i, b_ i \le N$) and $c_ i$ ($1 \le c_ i \le B+1$), which means that the $i$’th road connects the cities $a_ i$ and $b_ i$ has a cost of $c_ i$ crowns to put up posters along.
It’s guaranteed that a sequence of roads exist between any pair of paths.
Output
Output a single integer – the greatest number of people who can see your posters, if you put them up optimally.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
|
Group |
Points |
Constraints |
|
$1$ |
$10$ |
$N \le 15$, $B \le 500$ |
|
$2$ |
$10$ |
Each path has $c_ i = 1$ |
|
$3$ |
$10$ |
$B \le 500$, and each city has at most two adjacent roads. |
|
$4$ |
$15$ |
$N \le 100$, $B \le 500$, and each city has at most three adjacent roads, except city $1$ which has at most two. |
|
$5$ |
$20$ |
$N \le 100$, $B \le 500$ |
|
$6$ |
$35$ |
No additional constraints. |
Explanation of sample
In the first sample case it’s optimal to put up posters on the roads between city $1$ and $6$, and between city $2$ and $3$. This costs $350 + 100$ (less than the budget of $500$), and will result in everyone in cities $3$, $4$, $5$ and $6$ seeing the posters, a total of $1000 + 100 + 300 + 300 = 1700$ people.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 500 500 1000 100 300 300 1 2 200 3 2 100 1 6 350 5 6 501 6 4 250 |
1700 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 4 10 20 30 40 50 1 2 1 1 3 1 1 4 1 2 5 1 3 6 1 |
150 |
