== include(page="template/taskheader" task_id="confuzie") ==
“Been […] confused for so long it’s not true”
bq. Been […] confused for so long it’s not true
ZLed a devenit un pic confuz în ultima vreme, aşa că a început să se joace cu arbori (în scop terapeutic). Fiecare nod din arbore poate fi colorat fie cu alb, fie cu negru. Iniţial toate nodurile sunt colorate în alb.
Pe parcursul jocului, ZLed poate alege un nod din arbore căruia să îi schimbe culoarea (din alb în negru sau din negru în alb). De asemenea, el poate selecta două noduri x şi y din arbore, cu x strămoş al lui y, şi se poate întreba: ”Dintre toate nodurile de pe drumul de la x la y (inclusiv x şi y) care este cel mai apropiat nod faţă de x care este colorat în negru? ”.
Pe parcursul jocului, ZLed poate alege un nod din arbore căruia să îi schimbe culoarea (din alb în negru sau din negru în alb). De asemenea, el poate selecta două noduri $x$ şi $y$ din arbore, cu $x$ strămoş al lui $y$, şi se poate întreba: ”Dintre toate nodurile de pe drumul de la $x$ la $y$ (inclusiv $x$ şi $y$) care este cel mai apropiat nod faţă de $x$ care este colorat în negru? ”.
h2. Cerinta
Deoarece vreţi să disipaţi starea de confuzie a lui ZLed, trebuie să îl ajutaţi şi să-i rezolvaţi operaţiile de colorare a unui nod, respectiv de interogare a celui mai apropiat nod de culoare neagră de pe drumul de la x la y, pentru un strămoş x al lui y.
Deoarece vreţi să disipaţi starea de confuzie a lui ZLed, trebuie să îl ajutaţi şi să-i rezolvaţi operaţiile de colorare a unui nod, respectiv de interogare a celui mai apropiat nod de culoare neagră de pe drumul de la $x$ la $y$, pentru un strămoş $x$ al lui $y$.
h2. Date de intrare
Fişierul confuzie.in va conţine pe prima linie două numere N şi M, unde N este numărul de noduri din arbore, iar M numărul de operaţii care se efectuează, atât modificări de culoare, cât şi interogări.
Următoarele N-1 linii conţin descrierea arborelui, pe fiecare linie aflându-se două numere a şi b, semnificând faptul că există o muchie între a şi b în arbore.
Pe urmatoarele M linii sunt descrise operaţiile efectuate. Primul număr de pe fiecare din aceste linii reprezintă tipul operaţiei: 0 dacă este vorba de o modificare de culoare, respectiv 1 dacă este vorba de o interogare. În primul caz, după 0 va urma un număr x, semnificând că se va schimba culoarea lui x, din negru în alb sau din alb în negru. În al doilea caz, după 1 vor urma două numere x i ş y, cu x strămoş al lui y, semnificând că se doreşte aflarea, dintre toate nodurile de pe drumul de la x la y, a celui mai apropiat nod faţă de x care este colorat în negru.
Fişierul $confuzie.in$ va conţine pe prima linie două numere $N$ şi $M$, unde $N$ este numărul de noduri din arbore, iar $M$ numărul de operaţii care se efectuează, atât modificări de culoare, cât şi interogări.
Următoarele $N-1$ linii conţin descrierea arborelui, pe fiecare linie aflându-se două numere $a$ şi $b$, semnificând faptul că există o muchie între $a$ şi $b$ în arbore.
Pe urmatoarele $M$ linii sunt descrise operaţiile efectuate. Primul număr de pe fiecare din aceste linii reprezintă tipul operaţiei: 0 dacă este vorba de o modificare de culoare, respectiv 1 dacă este vorba de o interogare. În primul caz, după 0 va urma un număr $x$, semnificând că se va schimba culoarea lui $x$, din negru în alb sau din alb în negru. În al doilea caz, după 1 vor urma două numere $x$ $i$ şi $y$, cu $x$ strămoş al lui $y$, semnificând că se doreşte aflarea, dintre toate nodurile de pe drumul de la $x$ la $y$, a celui mai apropiat nod faţă de $x$ care este colorat în negru.
h2. Date de ieşire
Fişierul confuzie.out va conţine câte o linie pentru fiecare operaţie de interogare prezentă în fişierul de intrare. Această linie poate conţine fie nodul cerut(cel mai apropiat nod negru de x) de pe drumul dintre cele două noduri date la interogare, fie -1 dacă drumul dintre nodurile date la interogare nu con ine niciun nod colorat cu negru.
Fişierul $confuzie.out$ va conţine câte o linie pentru fiecare operaţie de interogare prezentă în fişierul de intrare. Această linie poate conţine fie nodul cerut(cel mai apropiat nod negru de $x$) de pe drumul dintre cele două noduri date la interogare, fie $-1$ dacă drumul dintre nodurile date la interogare nu conţine niciun nod colorat cu negru.
h2. Restricţii
* Rădăcina arborelui se consideră nodul cu indice 1.
* Rădăcina arborelui se consideră nodul cu indice $1$.
* $1$ ≤ $N$ ≤ $200.000$
* $1 ≤ $M$ ≤ $450.000$
* $1 ≤ $x$, $y$, $a$, $b$ ≤ $N$
* $1$ ≤ $M$ ≤ $450.000$
* $1$ ≤ $x$, $y$, $a$, $b$ ≤ $N$
* Un arbore este un graf neorientat, conex şi aciclic.
* Un nod $x$ se numeşte strămoş al lui $y$ dacă el se află pe drumul de la $y$ la rădăcina arborelui.
h2. Exemplu
table(example). |_. confuzie.in |_. confuzie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7 10
1 2
2 4
1 3
3 5
4 6
3 7
0 2
1 1 2
1 1 1
0 1
1 1 2
0 5
1 3 5
1 3 7
0 1
1 1 5
|2
-1
1
5
-1
5
|
h3. Explicaţie
...
Pe rand operatiile:
Setam $2$ pe negru
Din drumul $[1, 2]$, $2$ e negru
Din drumul $[1, 1]$, nu avem nod negru
Setam $1$ pe negru
Din drumul $[1, 2]$, $1$ si $2$ negre, primul este $1$
Setam $5$ pe negru
Din drumul $[3, 5]$, $5$ e negru
Din drumul $[3, 7]$ nu avem nod negru
Setam $1$ pe alb
Din drumul $[1, 3, 5]$, $5$ e negru
== include(page="template/taskfooter" task_id="confuzie") ==
