Fişierul intrare/ieşire:color4.in, color4.outSursăad-hoc
AutorIonut BogdanescuAdăugată deswift90Ionut Bogdanescu swift90
Timp execuţie pe test0.35 secLimită de memorie66048 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Color 4

Vine vacanta si Gigel s-a gandit sa nu mai stea atat de mult in fata calculatorului si sa se apuce de pictura. Totusi lui ii place atat de mult informatica incat vrea ca tablourile sale sa aiba legatura cu arborii cu radacina in nodul 1. Astfel toate tablourile sale vor fi sub forma unui arbore cu N noduri. Initial, toate nodurile vor fi avea culoarea 1. Dar Gigel nu este multumit si incearca sa-si faca tablourile mai interesante. Prin urmare, el poate sa coloreze un subarbore cu o culoare la alegerea sa. Din cand in cand este curios care este culoarea dominanta dintr-un subarbore si cate noduri au aceasta culoare. Totusi arborii pe care-i picteaza el pot avea dimensiuni impresionante asa ca va pune si pe voi sa-l ajutati.

Date de intrare

Pe prima linia a fisierului de intrare se afla 3 numere, N, M, C separate printr-un spatiu. N - numarul de noduri al arborelui, M - numarul de operatii, C - numarul maxim de culori pe care-l are Gigel la dispozitie. Urmeaza N-1 linii care descriu arborele, pe fiecare dintre acestea se afla 2 numere x si y cu semnificatia ca exista o muchie intre x si y. Urmeaza M linii care descriu operatiile dupa cum urmeaza:
- 0 x c - subarborele x este colorat cu culoarea c
- 1 x - culoarea dominanta in subarborele cu radacina in x si numarul de noduri care au acea culoare.

Date de ieşire

În fişierul de ieşire color4.out se vor gasi un numar de linii egal cu numarul operatiilor de tip 1 din fisierul de intrare. Pe fiecare linie se vor gasi 2 numere C A cu semnificatia: C - culoarea dominanta si A - numarul de noduri colorate in culoarea C.

Restricţii

  • 1 ≤ N ≤ 50.000
  • 1 ≤ M ≤ 10.000
  • 1 ≤ C ≤ 75
  • O culoare este dominanta intr-un subarbore daca are cele mai multe noduri colorate in acea culoare.
  • Daca exista mai multe culori care sunt dominante intr-un subarbore atunci se va afisa culoarea de indice minim.

Exemplu

color4.incolor4.out
11 7 3
10 11
6 7
11 7
11 9
4 8
8 2
10 3
10 4
4 1
5 9
0 11 2
1 1
1 10
0 4 3
0 9 1
0 7 2
1 10
1 6
2 5
3 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content