color4

Color 4

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

Poveste şi cerinţă...

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.

h2. Date de intrare

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

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.

h2. Date de ieşire

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

Î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.

h2. 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.

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

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

| 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

|

h3. Explicaţie
 
...
 

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

5931