CSES - Alipuut
  • Time limit: 1.00 s
  • Memory limit: 128 MB

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

Saat tehdä puuhun korkeintaan kk 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 nn ja kk: solmujen määrä ja poistojen määrä. Solmut on numeroitu 1,2,,n1,2,\ldots,n.

Sitten syötteessä on nn kokonaislukua h1,h2,,hnh_1,h_2,\ldots,h_n: jokaisen solmun arvo.

Lopuksi syötteessä on n1n-1 riviä, jotka kuvaavat puun rakenteen. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: solmu bb on solmun aa lapsi.

Tuloste

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

Rajat

  • 1n1051 \le n \le 10^5
  • 0kmin(10,n)0 \le k \le \min(10,n)
  • 109hi109-10^9 \le h_i \le 10^9
  • 1a,bn1 \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