CSES - Datatähti 2024 qualification mirror - Laskettelukeskus
  • Language:
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Lumimyrsky on iskenyt laskettelukeskukseen ja rinteet kaipaavat pikaista aurausta.

Laskettelukeskus koostuu nn rinteestä. Rinteet on yhdistetty toisiinsa yhteensä n1n-1 polulla siten, että rinne 11 on huipulla ja sieltä on alaspäin kulkeva reitti kaikille muille rinteille.

Lumiauralla voi kulkea rinteitä ja polkuja ainoastaan alaspäin ja aurata matkalle sattuvat rinteet. Jokaisesta rinteestä on tiedossa tarvittavien aurauskertojen määrä.

Lennätät helikopterilla lumiauroja vuoren huipulle. Mikä on pienin määrä lumiauroja, jolla kaikki rinteet saadaan aurattua?

Syöte

Ensimmäisellä rivillä on kokonaisluku nn: rinteiden määrä.

Seuraa n1n-1 riviä lukuja aa ja bb: rinteeltä aa on polku rinteelle bb. Rinteet on numeroitu 1,2,,n1,2,\dots,n.

Viimeisellä rivillä on nn lukua c1,c2,,cnc_1, c_2, \dots, c_n: tarvittavien aurauskertojen määrä rinteille 1,2,,n1,2,\dots,n.

Tuloste

Tulosta yksi kokonaisluku: pienin tarvittava määrä lumiauroja.

Esimerkki

Syöte:

5
1 2
1 3
3 4
3 5
0 2 4 3 1

Tuloste:

6

Selitys: Laskettelukeskus on havainnollistettu kuvassa.

Jos tarvitset tarkempaa kuvausta kuvan sisällöstä, voit lähettää viestin järjestelmässä kohdassa Messages.

22 lumiauraa kulkee reitin (1,2)(1,2), 33 lumiauraa reitin (1,3,4)(1,3,4) ja 1 lumiaura reitin (1,3,5)(1,3,5).

Osatehtävä 1 (53 pistettä)

  • 1n1001 \le n \le 100
  • 0ci1000 \le c_i \le 100

Osatehtävä 2 (47 pistettä)

  • 1n1000001 \le n \le 100\,000
  • 0ci1090 \le c_i \le 10^9