Fişierul intrare/ieşire:painting.in, painting.outSursăad-hoc
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Painting

Fie un arbore cu N noduri, fiecare nod avand o culoare. Initial, toate nodurile au culoarea 1. Pe acest arbore se fac M operatii de tipul: se coloreaza toate nodurile din subarborele lui X cu culoarea Y. Se considera ca radacina arborelui este nodul 1.
Culoarea unui nod este data de culoarea ultimei operatii aplicate nodului respectiv.

Care este culoarea fiecarui nod dupa executarea tuturor operatiilor?

Date de intrare

Fişierul de intrare painting.in va contine pe prima linie numerele N si M.
Urmatoarele N - 1 linii vor contine cate o pereche X Y, cu semnificatia ca exista muchie in arbore intre nodurile respective.
Urmatoarele M linii vor contine cate 2 numere X Y, cu semnificatia ca subarborele nodului X este colorat cu culoarea Y.

Date de ieşire

În fişierul de ieşire painting.out va contine N numere, al i-lea numar reprezentand culoarea nodului i.

Restricţii

  • 1 ≤ N, M ≤ 105
  • 1 ≤ Culoarea unui nod ≤ 104

Exemplu

painting.inpainting.out
7 4
1 2
1 3
2 4
2 5
4 6
3 7
2 7
4 5
3 9
5 4
1 7 9 5 4 5 9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?