Revizia anterioară Revizia următoare
| 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 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ţ.
Exemplu
| oxificare.in | oxificare.out |
|---|---|
| 2 4 1 2 3 5 5 5 4 1 2 3 5 4 5 | 5 6 |
Explicaţie
...
