== include(page="template/taskheader" task_id="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ă. Cele $N$ puncte *nu trebuie* sa fie neaparat distincte.
* 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ă.
 
Voi trebuie sa gasiti aceasta distanta minima.

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.

h2. 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:

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 conţine valoarea $N$, reprezentând numărul de noduri ale arborelui.

Prima linie va contine valoarea $N$, reprezentand numarul 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 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 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.

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.

h2. Date de ieşire

În fişierul de ieşire $oxificare.out$ se vor afla $T$ linii, a $i$-a linie reprezentand solutia pentru testul $i$.

Î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.

h2. Restricţii

* $1 ≤ N ≤ 1.000$
* $1 ≤ cost[i] ≤ 5.000$

* $1 ≤ N ≤ 3.000$
* $1 ≤ cost[i] ≤ 10.000$

* $1 ≤ parinte[i] ≤ i$

* Suma valorilor lui $N$ in cadrul aceluiasi fisier de intrare nu depaseste valoarea $3.000$.
* Toate valorile din input sunt numere naturale.
* Pentru teste in valoare de $50$ de puncte, se garantează în plus că $parinte[i] = i$ pentru toţi $1 ≤ i ≤ N - 1$. Cu alte cuvinte, arborele este un lanţ.
* Dintre acestea, pentru teste in valoare de $20$ de puncte, se garanteaza in plus ca $1 ≤ N, cost[i] ≤ 100$, respectiv $1 ≤ T ≤ 25$.

* 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.

h2. Exemplu
table(example). |_. oxificare.in |_. oxificare.out |

| 2
4
1 2 3
5 5 5

| 1

4
1 2 3
5 4 5

| 5
6

| 6

|
h3. Explicaţie

O solutie pentru primul test este lista de puncte ${1, 6, 1, 6}$.
O solutie pentru cel de al doilea test este lista de puncte ${0, 5, 1, 6}$.

...

== include(page="template/taskfooter" task_id="oxificare") ==