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

• $1 \le n \le 10^5$
  
• $0 \le k \le \min(10,n)$
  
• $-10^9 \le h_i \le 10^9$
  
• $1 \le a,b \le n$
  

Esimerkki

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

Tuloste:
2