hardtask

Hardtask

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

Se da un arbore cu N noduri si radacina in nodul 1, iar fiecare muchie are o valoare si M operatii de forma:
1 nod s -> valoarea muchiei dintre nod si tatal nodului devine s
2 nr k <tex> x_1 x_2 ... x_{nr} </tex> -> sa se afiseze numarul de perechi neordonate (x,y), cu x si y apartinand multimii citite de nr elemente, care au suma valorilor de pe drumul de la x la y divizibila cu k

Se da un arbore cu $N$ noduri, numerotate de la $1$ la $N$, si radacina sa in nodul $1$, iar fiecare muchie are o valoare si $M$ operatii de forma:
$1 nod s$ -> valoarea muchiei dintre $nod$ si tatal nodului devine $s$
$2 nr k x[~1~] x[~2~] ... x[~nr~]$ -> sa se afiseze numarul de perechi neordonate $(x,y)$, cu $x$ si $y$ apartinand multimii citite de $nr$ elemente, care au suma valorilor de pe drumul de la $x$ la $y$ divizibila cu $k$

h2. Date de intrare

Fişierul de intrare $hardtask.in$ contine pe prima linie numerele naturale N si M despartite printr-un spatiu. Pe liniile de la 2 la N se afla cate 2 numere naturale tata si val reprezentand tatal nodului i, respectiv valoarea muchiei intre nodul i si tatal acestuia. Pe urmatoarele M linii se afla cate o operatie: prima valoare este tip, iar daca tip este 1 atunci urmeaza 2 numere naturale nod si s cu semnificatiile de mai sus, iar daca tip este 2 atunci urmeaza 2 numere naturale nr si k cu semnificatiile anterioare si un sir de nr numere distincte reprezentand multimea de noduri.

Fişierul de intrare $hardtask.in$ contine pe prima linie numerele naturale $N$ si $M$ despartite printr-un spatiu. Pe liniile de la $2$ la $N$ se afla cate $2$ numere naturale $tata$ si $val$ reprezentand tatal nodului $i$, respectiv valoarea muchiei intre nodul $i$ si tatal acestuia. Pe urmatoarele $M$ linii se afla cate o operatie: prima valoare este $tip$, iar daca $tip$ este $1$ atunci urmeaza $2$ numere naturale $nod$ si $s$ cu semnificatiile de mai sus, iar daca tip este $2$ atunci urmeaza $2$ numere naturale $nr$ si $k$ cu semnificatiile anterioare si un sir de $nr$ numere distincte reprezentand multimea de noduri.

h2. Date de ieşire

În fişierul de ieşire $hardtask.out$ se va afisa raspunsul pentru operatiile de tipul 2, fiecare pe cate o linie.

În fişierul de ieşire $hardtask.out$ se va afisa raspunsul pentru operatiile de tipul $2$, fiecare pe cate o linie.

h2. Restricţii

* N, M &le; <tex>10^5</tex>
* Suma nr-urilor &le; <tex>10^5</tex>
* 1 &le; k &le; <tex>10^9</tex>
* 0 &le; s, val &le; <tex>10^9</tex>
* **numarul de perechi si suma valorilor muchiilor depasesc tipul de date int**

* $1 ≤ N, M ≤ 10^5^$
* $Suma nr-urilor ≤ 10^5^$
* $1 ≤ k ≤ 10^9^$
* $0 ≤ s, val ≤ 10^9^$
* $**Numarul de perechi si suma valorilor muchiilor depasesc tipul de date int**$
* $Pentru fiecare injuratura adresata comisiei pentru aceasta problema, George va incepe sa sughite!$

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

| 11

| 11 4

  1 2
  1 1
  2 3

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

| This is another
  text written on
  multiple lines.

| 4
  6
  2

|
h3. Explicaţie