== include(page="template/taskheader" task_id="dosare") ==
Poveste si cerinta...
Spre deosebire de prietenii sai - Miruna si Algorel - care isi pierd timpul cu bile si bilute, Haralambie este mult mai practic in prag de Craciun: el s-a decis sa-si optimizeze sistemul de fisiere.
Dosarele de pe calculatorul lui Haralambie sunt organizate ierarhic. In dosarul principal se afla mai multe dosare, care la randul lor contin alte dosare, s.a.m.d. El foloseste doar tastatura pentru a se deplasa prin ele, asa ca este foarte importanta ordinea in care se afla subdosarele intr-un dosar. Pentru a intra intr-un subdosar al unui dosar, Haralambie trebuie sa apese tasta de navigare in jos (sageata jos) pana cand se afla deasupra subdosarului dorit.
Spre exemplu, daca in dosarul principal, numerotat cu 1, se afla, in aceasta ordine, dosarele 2, 3 si 4, si in dosarul 3 se afla dosarele 5, 6 si 7, pentru a accesa dosarul 7, Haralambie trebuie sa apese tasta $ENTER$ pentru a intra in 1, sa apese sageata jos o data pana ajunge pe 3, din nou $ENTER$ pentru a intra in 3, apoi de doua ori sageata in jos, si inca o data $ENTER$ pentru a intra in 7, deci in total 6 apasari de taste.
Haralambie cunoaste pentru fiecare dosar in parte de cate ori va avea nevoie sa acceseze acel dosar si va promite sa va cinsteasca cu bile colorate daca veti ordona subdosarele in dosare in asa fel incat numarul total de apasari de taste sa fie minim. La fiecare accesare a unui dosar, considerati ca Haralambie va porni din dosarul principal.
h2. Date de intrare
Fisierul de intrare $dosare.in$ ...
Fisierul de intrare $dosare.in$ contine pe prima linie numarul total de dosare, $N$. Pe urmatoarele $N$-1 linii se afla informatiile referitoare la ierarhia sistemului de dosare. Pe linia $i$ se afla dosarul parinte al dosarului $i$. Dosarul principal are numarul de ordine 1. Pe ultima linie a fisierului de intrare se afla $N$ numere intregi, reprezentand numarul de accesari al fiecarui dosar.
h2. Date de iesire
In fisierul de iesire $dosare.out$ ...
In fisierul de iesire $dosare.out$ se va afla pe singura linie numarul total minim de apasari.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 16000$
* $1 ≤ A{~i~} ≤ 1000000$
* Pentru $40%$ din teste $1 ≤ N ≤ 333$
h2. Exemplu
table(example). |_. dosare.in |_. dosare.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 9
1
1
1
3
3
3
4
4
1 1 1 1 1 1 1 1 1
| 31
|
h3. Explicatie
...
Dosarul 1 contine dosarele 2, 3 si 4. In dosarul 3 avem dosarele 5, 6 si 7 iar in dosarul 4 avem dosarele 8 si 9.
Putem aseza dosarele in urmatorul mod: in dosarul 3 vom aseza subdosarele in ordinea 5, 6, 7, in dosarul 4 in ordinea 8, 9, iar in dosarul 1 in ordinea 3, 4, 2.
Conform acestei asezari, scorul total va fi: 1*1 + 1*4 + 1*2 + 1*3 + 1*3 + 1*4 + 1*5 + 1*4 + 1*5 = 31. Orice alta asezare va rezulta intr-un numar total cel putin egal cu 31.
== include(page="template/taskfooter" task_id="dosare") ==
