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 dă un arbore cu costuri pe muchii. Acest arbore trebuie să fie "liniarizat" pe axa numerelor reale, în următorul sens:

• Fiecărui nod din arbore îi va fi asociat exact un punct de pe axă.
• Dacă între două noduri X şi Y există muchie în arbore, atunci distanţa dintre punctele asociate acestor noduri trebuie să fie egală cu costul muchiei dintre ele.
• Distanţa maximă dintre două puncte asociate nodurilor trebuie să fie minimă.

Date de intrare

Fişierul de intrare oxificare.in va conţine pe prima sa linie valoarea întreagă T, reprezentând numărul de teste din fişier. Structura unui test este următoarea:

Prima linie va conţine valoarea N, reprezentând numărul de noduri ale arborelui.

Cea de a doua linie va conţine şirul parinte. Acesta este format din N - 1 valori, parinte[i] reprezentând părintele nodului i + 1 în arbore. Nodul 1 este rădăcina arborelui şi nu are părinte. A se nota că arborele este descris în acest fel doar cu scopul de a simplifica inputul, rădăcina fiind irelevantă in procesul de liniarizare a arborelui.

Cea de a treia linie va conţine la rândul ei un şir cost de N - 1 valori, unde cost[i] reprezintă costul muchiei dintre nodul i + 1 si părintele său.

Date de ieşire

În fişierul de ieşire oxificare.out se va afla o singura valoare, reprezentând distanţa maximă minim posibilă în cazul unei liniarizări optime a arborelui.

Restricţii

• 1 ≤ N ≤ 1.000
• 1 ≤ cost[i] ≤ 5.000
• 1 ≤ parinte[i] ≤ i
• Suma valorilor lui N in cadrul aceluiasi fisier de intrare nu depaseste valoarea 3.000.
• Pentru teste in valoare de X puncte, se garantează în plus că parinte[i] = i pentru toţi 1 ≤ i ≤ N - 1. Cu alte cuvinte, arborele este un lanţ.

Exemplu

Explicaţie

...

Cum se trimit solutii?