Fişierul intrare/ieşire:hardtask.in, hardtask.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 16
AutorChichirim GeorgeAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test1.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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 x1 x2 ... xnr -> 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

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.

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.

Restricţii

  • 1 ≤ N, M ≤ 105
  • Suma nr-urilor ≤ 105
  • 1 ≤ k ≤ 109
  • 0 ≤ s, val ≤ 109
  • 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!

Exemplu

hardtask.inhardtask.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

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?