== include(page="template/taskheader" task_id="hardtask") ==
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$
Poveste şi cerinţă...
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$ ...
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$ ...
h2. Restricţii
* $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 4
1 2
1 1
2 3
2 4
3 1
3 2
1 5
8 3
5 3
5 2
2 5 3 2 4 5 10 11
1 5 3
2 5 3 2 4 5 10 11
2 4 2 1 3 6 7
| 4
6
2
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
