Fişierul intrare/ieşire:parb.in, parb.outSursăAlgoritmiada 2013, Runda Finala
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inparb.out
5
zabac
1 2
2 3
1 4
4 5
zac
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?