| Fişierul intrare/ieşire: | parb.in, parb.out | Sursă | Algoritmiada 2013, Runda Finala |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
Parb
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.
Date de intrare
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.
Date de ieşire
Fişierul de ieşire parb.out va contine pe o linie un sir de caractere reprezentand Parb(x,y).
Restricţii
- 1 ≤ N ≤ 500.000
- Nodul 1 este radacina arborelui
- Un sir (x1,x2...xN) este mai mic din punct de vedere lexicografic decat un alt sir (y1,y2...yM) daca exista o pozitie p astfel incat xp < yp si x1 = y1, x2 = y2 ... xp-1 = yp-1 sau N < M si x1 = y1, x2 = y2 ... xN = yN
Exemplu
| parb.in | parb.out |
|---|---|
| 5 zabac 1 2 2 3 1 4 4 5 | zac |
