Code Submission Evaluation System Login

Datatähti-valmennus

Alipuut


Task | Statistics


CSES - Alipuut

Time limit:1.00 s Memory limit:128 MB

Sinulle on annettuna puu, jossa on $n$ solmua. Solmu 1 on puun juuri, ja jokaisella solmulla on tietty arvo.

Saat tehdä puuhun korkeintaan $k$ poistoa. Jokaisessa poistossa saat valita minkä tahansa puun alipuun ja poistaa sen puusta.

Mikä on suurin mahdollinen solmujen arvojen summa poistojen jälkeen?

Syöte

Syötteen alussa on kaksi kokonaislukua $n$ ja $k$: solmujen määrä ja poistojen määrä. Solmut on numeroitu $1,2,\ldots,n$.

Sitten syötteessä on $n$ kokonaislukua $h_1,h_2,\ldots,h_n$: jokaisen solmun arvo.

Lopuksi syötteessä on $n-1$ riviä, jotka kuvaavat puun rakenteen. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: solmu $b$ on solmun $a$ lapsi.

Tuloste

Tulosta yksi kokonaisluku: suurin arvojen summa poistojen jälkeen.

Rajat
Esimerkki

Syöte:
5 2
2 -3 -9 5 3
1 2
1 3
3 4
3 5


Tuloste:
2