Fişierul intrare/ieşire:posta3.in, posta3.outSursăLot Resița 2012 - Baraj 3 Seniori
AutorAndrei CiocanAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test0.05 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Posta3

Sistemul poştal este alcătuit din poşta centrală şi din sucursale. Acest sistem este reprezentat ca un arbore, având nodurile etichetate cu 1, 2, ..., N, aşezate pe nivele, în rădăcină fiind poşta centrală, iar în celelalte noduri sucursalele. Astfel putem vorbi, prin analogie cu noţiunile din teoria grafurilor, despre poştă rădăcină, respectiv poştă fiu. Coletele poştale sunt identificate prin coduri numerice. La un moment dat în poşta centrală şi în fiecare sucursală se află câte un singur colet. Sistemul de expediere al coletelor se realizează cu un singur tip de operaţii: coletul aflat în poşta rădăcină este expediat, locul lui fiind luat de coletul care are codul de valoare maximă aflat în una dintre poştele fii; astfel în poşta fiu, locul coletului expediat va fi luat de coletul care are codul de valoare maximă aflat în poştele fii şi aşa mai departe, până se ajunge la o poştă fără posibilitate de a prelua un colet.

Pentru a putea trimite un colet important cu prioripost poşta va folosi acelaşi tip de operaţii, însă poate schimba codul anumitor colete, inclusiv al coletului important, pentru a reduce numărul de operaţii prin care acesta va ajunge la poşta centrală în vederea difuzării. 

Cerinţă

Determinaţi numărul minim de colete ale căror coduri trebuiesc schimbate favorabil, astfel încât coletul din nodul etichetat cu X să ajungă în poşta centrală, după un număr minim de operaţii.

Date de intrare

Pe prima linie a fişierului posta.in se afla două numere naturale N şi X, numărul de noduri ale arborelui asociat sistemului poştal, respectiv eticheta asociată poştei. Pe următoarele N-1 linii este descris arborele sistemului poştal, fiecare linie conţinând două numere naturale a şi b, însemnând că poşta b este poştă fiu al lui a. Pe linia N+1 se află n numere naturale, a i-a dintre aceste valori reprezentând codul coletului din poşta aflată în nodul i.

Date de ieşire

Fisierul posta.out va conţine o singură valoare, şi anume numărul minim de coduri schimbate.

Restricţii

  • 1 ≤ N ≤ 3 000
  • Codurile iniţiale sunt două câte două distincte.
  • Codurile se pot schimba in orice altă valoare.
  • Arborele nu este neapărat binar.
  • Iniţial codurile sunt numere naturale cu maxim 9 cifre.

Exemplu

posta3.inposta3.outExplicaţie
7 7
1 2
1 3
2 4
2 5
3 6
5 7
5 6 4 3 8 9 2
1
Datele de intrare corespund primei figuri din exemplul de mai sus. Dacă schimbăm codul coletului de la poşta 7
din 2 în 10, numărul de operaţii va fi
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content