parb

Parb

== include(page="template/taskheader" task_id="parb") ==

Poveste şi cerinţă...

Se da un arbore cu $N$ noduri. In fiecare nod se afla cate un caracter de la $'a'$ la $'z'$. Fie functia $Parb(x,y)$ ce returneaza sirul de caractere format de pe lantul de la nodul $x$ la nodul $y$. Nodul $x$ trebuie obligatoriu sa fie stramos al nodului $y$. Sa se determine $2$ noduri $x$ si $y$ astfel incat sirul returnat de functia $Parb(x,y)$ sa fie maxim lexicografic.

h2. Date de intrare

Fişierul de intrare $parb.in$ ...

Fişierul de intrare $parb.in$ va contine pe prima linie un numar natural $N$. Pe a $2$-a linie vor fi $N$ caractere de la $'a'$ la $'z'$ fara spatiu intre ele. Nodul $i$ contine caracterul al $i$-lea din acest sir. Pe urmatoarele $N - 1$ linii vor fi cate $2$ numere $a$ si $b$ reprezentand faptul ca exista muchie intre nodul $a$ si nodul $b$.

h2. Date de ieşire

În fişierul de ieşire $parb.out$ ...

Fişierul de ieşire $parb.out$ va contine pe o linie un sir de caractere reprezentand $Parb(x,y)$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 500.000$
* Nodul $1$ este radacina arborelui
* Un sir {$(x{~1~},x{~2~}...x{~N~})$} este mai mic din punct de vedere lexicografic decat un alt sir {$(y{~1~},y{~2~}...y{~M~})$} daca exista o pozitie $p$ astfel incat {$x{~p~} < y{~p~}$} si {$x{~1~} = y{~1~}$}, {$x{~2~} = y{~2~}$} ... {$x{~p-1~} = y{~p-1~}$} sau $N < M$ si {$x{~1~} = y{~1~}$}, {$x{~2~} = y{~2~}$} ... {$x{~N~} = y{~N~}$}
 

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|5
zabac
1 2
2 3
1 4
4 5
| zac

|

h3. Explicaţie
 
...

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