Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | arbore5.in, arbore5.out | Sursă | Infoarena Monthly 2012, Runda 4 |
| Autor | Silviu Popescu | Adăugată de |  Mr. Noname •cezar305 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arbore5
Gradinarul Marian detine un arbore cu N noduri, fiecare muchie fiind initial vopsita in alb. Marian fiind plecat de acasa, prietenul sau cel mai bun, Marius, strica frumusetea de arbore aplicand M operatii de tipul: alege o pereche de noduri (a, b) si vopseste toate muchiile de pe drumul ce uneste nodul a cu nodul b in felul urmator: daca muchia avea culoarea alba, Marius o vopseste in negru si invers, daca avea culoarea neagra, o vopseste in alb.
Din pacate pentru gradinarul Marian, cand a ajuns acasa era deja prea tarziu, Marius terminand de efectuat toate cele M operatii. Ingrozit, Marian vrea sa afle cate muchii mai au acum culoarea alba.
Cerinta
Determinati cate muchii din arbore au culoarea alba dupa efectuarea tuturor celor M operatii.
Date de intrare
Fişierul de intrare arbore5.in contine pe prima linie doua numere naturale N si M, separate prin cate un spatiu, reprezentand numarul de noduri ale arborelui detinut de gradinarul Marian, respectiv numarul de operatii efectuate de Marius. Pe urmatoarele N-1 linii se afla cate o pereche de numere x y, separate prin cate un spatiu, reprezentand faptul ca in arbore exista o muchie de la nodul x la nodul y. Pe urmatoarele M linii se afla cate o pereche de numere a b, separate prin cate un spatiu, cu proprietatea ca toate muchiile de pe drumul care incepe la nodul a si se termina la nodul b isi schimba culoarea.
Date de ieşire
În fişierul de ieşire arbore5.out trebuie sa existe pe prima linie un singur numar natural, reprezentand cate muchii au culoarea alba dupa efectuarea tuturor celor M operatii.
Restricţii
- 2 ≤ N ≤ 1.000.000
- 1 ≤ M ≤ 1.000.000
- Operatiile efectuate de Marius se executa in ordinea din fisierul de intrare.
Exemplu
| arbore5.in | arbore5.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
