== include(page="template/taskheader" task_id="turism2") ==
Poveste si cerinta...
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 $C{~i~}$, 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.
h2. Cerinta
Determinati pentru cele doua fete care este numarul total maxim de obiective pe care le pot vizita, respectand conditiile din enunt.
h2. Date de intrare
Fisierul de intrare $turism2.in$ ...
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 $C{~1~} C{~2~} C{~3~} ... C{~N-1~} C{~N~}$, 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.
h2. Date de iesire
In fisierul de iesire $turism2.out$ ...
Fisierul de iesire $turism2.out$ va contine $12$ linii, pe linia $i$ aflandu-se raspunsul pentru al $i$-lea set de date de intrare.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 100000$
* $1 ≤ C{~i~} ≤ 9999$
* Toate numerele din fisierul de intrare sunt numere naturale.
h2. Exemplu
table(example). |_. turism2.in |_. turism2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|2
1 1
1 2
...
3
1 2 3
1 2
1 3
|2
...
6
|
h3. 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.
== include(page="template/taskfooter" task_id="turism2") ==
