- Time limit: 1.00 s
- Memory limit: 128 MB
Sinulle on annettuna puu, jossa on solmua. Solmu 1 on puun juuri, ja jokaisella solmulla on tietty arvo.
Saat tehdä puuhun korkeintaan 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 ja : solmujen määrä ja poistojen määrä. Solmut on numeroitu .
Sitten syötteessä on kokonaislukua : jokaisen solmun arvo.
Lopuksi syötteessä on riviä, jotka kuvaavat puun rakenteen. Jokaisella rivillä on kaksi kokonaislukua ja : solmu on solmun 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