Fişierul intrare/ieşire:	oxificare.in, oxificare.out	Sursă	Algoritmiada 2017, Runda Finala, Seniors
Autor	Andrei Popa, Radu Muntean	Adăugată de	Mihai Calancea •klamathix
Timp execuţie pe test	0.9 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Oxificare

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

Explicaţie

...

Cum se trimit solutii?