harb

Colegiul Național “Frații Buzești”
Centrul de Pregătire pentru Performanță în Informatică
InfoCNFB - Ediția a II-a, Seniori
9 decembrie 2023

Cerință

Se dă un număr $T$ egal cu $1$ sau $2$.
Se dă în continuare un graf cu $N$ noduri care are structura unei păduri de arbori cu radacină. Aceasta este reprezentată printr-un vector de tați $\text{parent}$ astfel:

• $\text{parent}[\text{nod}] = \text{nod}$, dacă nodul curent este rădăcina unui arbore din pădure;
• $\text{parent}[\text{nod}] = \text{par}$, dacă nodul nu este radacină.

Pe această pădure de arbori se vor executa $M$ operații de urmatoarea formă:
(ATENȚIE, valorile $x$ și/sau $y$, acolo unde este cazul, nu se vor citi explicit, ci ele trebuie calculate conform unei formule bazate atât pe valorile $T$, $\text{coef\_x}$ și/sau $\text{coef\_y}$, cât și pe răspunsul la ultima întrebare, așa cum este explicat mai jos).

• 1 coef_x coef_y - $\text{parent}[x]$ devine $y$ (se garantează că în urma acestei operații graful va continua să aibă forma unei păduri de arbori);
• 2 coef_x - se va afișa numărul de noduri de pe lanțul de la nodul $x$ la rădăcina arborelui din care face parte $x$;
• 3 coef_x - se va afișa dimensiunea (ca număr de noduri) a arborelui din care face parte nodul $x$;
• 4 - se va afișa dimensiunea celui mai mare arbore din pădure;
• 5 coef_x coef_y - se va afișa $\text{lca}(x, y)$ dacă $x$ și $y$ fac parte din același arbore, altfel se va afișa $0$.

Formula de generare a lui x și/sau y în funcție de T, coef_x, coef_y:

• $T = 1$: x = coef_x; y = coef_y.
• $T = 2$:
  • Fie $p$ răspunsul la ultima întrebare de tip $2$, $3$, $4$ sau $5$ (inițial $p = 0$);
  • x = coef_x ^ p; y = coef_y ^ p (am notat prin ^ operatia XOR pe biți între două valori);
  • Daca query-ul curent este de tipul $2$, $3$, $4$ sau $5$, atunci p va deveni răspunsul la acest query.

Date de intrare

Pe prima linie a fișierului harb.in se află numărul $T$. Pe următoarea linie se află un număr $N$.
Pe următoarea linie se află $N$ numere reprezentând elementele vectorului $\text{parent}$.
Pe următoarea linie se află $M$ reprezentând numărul de operații la care trebuie să se răspundă.
Urmează $M$ linii care vor descrie cele $M$ operații, câte una pe fiecare linie.

Date de ieșire

În fișierul harb.out se vor scrie pe câte o linie răspunsul la fiecare întrebare de tip $2$, $3$, $4$ sau $5$.

Restricții și precizări

Exemplul 1

harb.in

1
14
1 1 1 2 3 3 7 8 8 8 8 11 11 13
20
5 4 6
5 6 5
5 12 14
2 11
2 4
3 11
3 4
4
2 14
1 13 2
1 3 7
1 7 9
2 6
5 5 6
3 6
3 14
5 14 4
4
2 12
2 13

harb.out

1
3
11
2
3
7
6
7
4
5
3
9
5
2
9
3
3

Explicație

Pădurea inițială de arbori arată ca în figura de mai jos:

$\text{lca}(4, 6) = 1$, $\text{lca}(12, 14) = 11$, lungimea lanțului de la $4$ la $1$ este $3$, arborele care îl conține pe $11$ are $7$ noduri, cel care îl conține pe $4$ are $6$ noduri, iar pentru query-ul de tip $4$, cel mai mare arbore are $7$ noduri, etc.

În urma celor $3$ operații de modificare a părinților, pădurea de arbori va arăta așa:

$\text{lca}(14, 4) = 2$, $\text{lca}(5, 6) = 3$, arborele care îl conține pe $6$ are $9$ noduri, iar cel care îl conține pe $14$ are $5$ noduri, lanțul de la nodul $6$ la nodul $8$ are lungimea $5$, etc.

Exemplul 2

harb.in

2
14
1 1 1 2 3 3 7 8 8 8 8 11 11 13 
20
5 4 6
5 7 4
5 15 13
2 0
2 6
3 8
3 3
4
2 9
1 9 6
1 7 3
1 3 13
2 2
5 0 3
3 5
3 7
5 11 1
4
2 5
2 14

harb.out

1
3
11
2
3
7
6
7
4
5
3
9
5
2
9
3
3

Explicație

Acest exemplu este identic cu primul, singura diferență fiind faptul că inputul este dat conform formulelor pentru $T=2$.