| Fişierul intrare/ieşire: | turism2.in, turism2.out | Sursă | Lot 2008 - Piatra Neamt, Baraj2 |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 1 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Turism2
Andreea si Ioana au ajuns in judetul Tinichea si doresc sa viziteze cat mai multe obiective turistice. Judetul Tinichea este format din N orase, intre unele dintre aceste orase existand sosele bidirectionale. Mai exact, orice sosea leaga direct doua orase, iar soselele sunt dispuse astfel incat intre oricare doua orase din judet sa existe un drum unic. Un drum este o succesiune de orase astfel incat intre oricare doua orase consecutive pe drum exista o sosea ce le leaga. Orasele sunt numerotate de la 1 la N si pentru fiecare oras se cunoaste Ci, numarul de obiective turistice din orasul i. Fiindca s-au certat putin in ultima vreme, cele doua fete vor sa aleaga fiecare cate un drum astfel incat numarul de obiective pe care le viziteaza Andreea adunat cu numarul de obiective pe care le viziteaza Ioana sa fie maxim. Conditiile pe care le pun fetele sunt ca drumurile lor sa nu aibe niciun oras in comun, iar orice oras sa fie vizitat cel mult o singura data.
Cerinta
Determinati pentru cele doua fete care este numarul total maxim de obiective pe care le pot vizita, respectand conditiile din enunt.
Date de intrare
Fisierul de intrare turism2.in va contine 12 seturi de date de intrare. Prima linie a unui set de date de intrare va contine numarul natural N, reprezentand numarul de orase. Pe urmatoarea linie a setului de date se vor afla N numere naturale C1 C2 C3 ... CN-1 CN, reprezentand, in ordine, numarul de obiective turistice din fiecare oras. Urmeaza N-1 linii pe care se afla cate doua numere naturale distincte A B cu semnificatia ca exista o sosea intre orasele A si B. Valorile de pe aceeasi linie sunt separate prin spatiu.
Date de iesire
Fisierul de iesire turism2.out va contine 12 linii, pe linia i aflandu-se raspunsul pentru al i-lea set de date de intrare.
Restrictii
- 2 ≤ N ≤ 100000
- 1 ≤ Ci ≤ 9999
- Toate numerele din fisierul de intrare sunt numere naturale.
Exemplu
| turism2.in | turism2.out |
|---|---|
| 2 1 1 1 2 ... 3 1 2 3 1 2 1 3 | 2 ... 6 |
Explicatie
Fisierul de intrare trebuie sa contina 12 teste, in exemplu sunt prezentate doar primul si ultimul dintre cele 12. Pentru primul test exista 2 orase, in fiecare oras fiind cate un obiectiv turistic. Exista o singura sosea (de la 1 la 2). Solutia optima este 2 (fiecare fata viziteaza cate un oras).
Pentru ultimul test exista 3 orase, avand 1, 2 respectiv 3 obiective turistice) si 2 sosele (intre 1 si 2, respectiv intre 1 si 3). Solutia optima este 6. Punctele de suspensie (...) indica faptul ca lipsesc cele 10 teste.
