Fişierul intrare/ieşire:oxificare.in, oxificare.outSursăAlgoritmiada 2017, Runda Finala, Seniors
AutorAndrei Popa, Radu MunteanAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.9 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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ă. 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.

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 vor afla T linii, a i-a linie reprezentand solutia pentru testul i.

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

Exemplu

oxificare.inoxificare.out
2
4
1 2 3
5 5 5
4
1 2 3
5 4 5
5
6

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?