Programmeringsolympiadens lägertävling 2019

Start

2019-02-03 09:30 CET

Programmeringsolympiadens lägertävling 2019

End

2019-02-03 14:30 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -291 days 23:31:44

Time elapsed

5:00:00

Time remaining

0:00:00

Problem C
Trädreklam

I Azerbajdzjan finns det $N$ städer, numrerade mellan $1$ och $N$, anslutna med $N - 1$ vägar så att varje stad kan nås från varje annan stad längs en sekvens av vägar. Det är snart dags för årets IOI i huvudstaden Baku (stad $1$) och alla i hela landet kommer då köra från sin hemstad till huvudstaden för att titta på tävlingen.

Du vill använda detta tillfälle för att marknadsföra din nya, jättesmarta tävlingsprogrammeringsdomare genom att sätta upp reklamplakat på massa träd längs olika vägar. Om du sätter upp plakat längs en viss väg kommer alla de personer som åker längs vägen någon gång under resan från sin hemstad till huvudstaden se plakatet.

Du har bedömt att det inte tillför någonting om en person ser dina plakat mer än en gång under sin färd – din domare är så imponerande att alla vill använda den efter att ha sett plakatet en enda gång! Varje väg har en viss kostnad för att sätta upp plakat på alla träd längs vägen, varje stad har en viss befolkningsmängd, och du har en begränsad budget. Om du sätter upp plakat optimalt, vad är det största antalet personer som kommer se minst ett plakat under sin färd till huvudstaden?

Indata

Den första raden innehåller två heltal – antalet städer $N$ ($1 \le N \le 2\, 000$) och din budget i kronor $B$ ($1 \le B \le 30\, 000$).

Den andra raden innehåller de $N-1$ talen $p_2, p_3, \dots , p_ N$ ($0 \le p_ i \le 30\, 000$). $p_ i$ är antalet personer som bor i stad $i$.

De följande $N-1$ raderna beskriver alla vägar i Azerbajdzjan. Den $i$:te av dessa rader innehåller heltalen $a_ i, b_ i$ ($1 \le a_ i, b_ i \le N$) och $c_ i$ ($1 \le c_ i \le B+1$), vilket innebär att det den $i$:te vägen går mellan städerna $a_ i$ och $b_ i$ och kostar $c_ i$ kronor att sätta upp plakat längs.

Det är garanterat att det går att ta sig mellan alla städer med hjälp av dessa vägar.

Utdata

Skriv ut ett enda tal: det största antal personer som kan se dina plakat, om du sätter ut dem optimalt.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

$1$

$10$

$N \le 15$, $B \le 500$

$2$

$10$

Varje väg har $c_ i = 1$

$3$

$10$

$B \le 500$, och varje stad har högst två angränsande vägar

$4$

$15$

$N \le 100$, $B \le 500$, och varje stad har högst tre angränsande vägar, utom stad $1$ som har högst två

$5$

$20$

$N \le 100$, $B \le 500$

$6$

$35$

Inga ytterligare begränsningar

Förklaring av exempelfall

I det första exemplet är det optimalt att sätta upp ett plakat på vägen mellan stad $1$ och $6$, och en mellan stad $2$ och $3$. Detta kostar $350 + 100$ (vilket klarar sig inom budgeten på $500$), och gör att personerna i städerna $3$, $4$, $5$ och $6$ kommer att se reklamen – totalt $1000 + 100 + 300 + 300 = 1700$ personer.

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