== 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:

<tex>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</tex>

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