Revizia anterioară Revizia următoare
Vi se da un arbore cu costuri pe muchii. Acest arbore trebuie sa fie "liniarizat" pe axa numerelor reale, in urmatorul sens:
- Fiecarui nod din arbore ii va fi asociat exact un punct de pe axa.
- Daca intre doua noduri X si Y exista muchie in arbore, atunci distanta dintre punctele asociate acestor noduri trebuie sa fie egala cu costul muchiei dintre ele.
- Distanta maxima dintre doua puncte asociate nodurilor trebuie sa fie minima.
Date de intrare
Fişierul de intrare oxificare.in va contine pe prima sa linie valoarea intreaga T, reprezentand numarul de teste din fisier. Structura unui test este urmatoarea:
Prima linie va contine valoarea N, reprezentand numarul de noduri ale arborelui.
Cea de a doua linie va contine sirul parinte. Acesta este format din N - 1 valori, parinte[i] reprezentand parintele nodului i + 1 in arbore. Nodul 1 este radacina arborelui si nu are parinte. A se nota ca arborele este descris in acest fel doar cu scopul de a simplifica inputul, radacina fiind irelevanta in procesul de liniarizare a arborelui.
Cea de a treia linie va contine la randul ei un sir cost de N - 1 valori, unde cost[i] reprezinta costul muchiei dintre nodul i + 1 si parintele sau.
Date de ieşire
În fişierul de ieşire oxificare.out se va afla o singura valoare, reprezentand distanta maxima minim posibila in cazul unei liniarizari optime a arborelui.
Restricţii
- 1 ≤ N ≤ 3.000
- 1 ≤ cost[i] ≤ 10.000
- 1 ≤ parinte[i] ≤ i
- Pentru teste in valoare de X puncte, se garanteaza in plus ca parinte[i] = i pentru toti 1 ≤ i ≤ N - 1. Cu alte cuvinte, arborele este un lant.
Exemplu
| oxificare.in | oxificare.out |
|---|---|
| 1 4 1 2 3 5 4 5 | 6 |
Explicaţie
...
