Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-04-13 12:34:16.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:arbore5.in, arbore5.outSursăInfoarena Monthly 2012, Runda 4
AutorSilviu PopescuAdăugată decezar305Mr. Noname cezar305
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Arbore5

Grădinarul Marian deţine un arbore cu N noduri, fiecare muchie fiind iniţial vopsită in alb. Marian fiind plecat de acasă, prietenul său cel mai bun, Marius, strică frumuseţea de arbore aplicând M operaţii de tipul: alege o pereche de noduri (a, b) şi vopseşte toate muchiile de pe drumul ce uneşte nodul a cu nodul b în felul următor: dacă muchia avea culoarea albă, Marius o vopseste in negru şi invers, dacă avea culoarea neagră, o vopseste in alb.
Din păcate pentru grădinarul Marian, cand a ajuns acasă era deja prea târziu, Marius terminând de efectuat toate cele M operatii. Ingrozit, Marian vrea să afle câte muchii mai au acum culoarea albă.

Cerinţă

Determinaţi câte muchii din arbore au culoarea albă după efectuarea tuturor celor M operaţii.

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.inarbore5.out
8 2
1 2
3 2
2 4
1 5
6 1
5 7
5 8
4 5
7 3
4

Explicaţie

Prima operatie schimba culoarea muchiilor dintre nodurile: (4, 2), (2, 1), (1, 5), toate acestea avand acum culoarea neagra (ele fiind initial albe).
A doua operatie schimba culoarea muchiilor dintre nodurile: (7, 5), (5, 1), (1, 2), (2, 3), astfel muchiile (7, 5) si (2, 3) devin neagre (inaintea acestei operatii fiind albe), iar muchiile (5, 1) si (1, 2) devin albe (ele fiind negre din cauza operatiei precedente).
Astfel, dupa aplicarea celor doua operatii, numarul de muchii albe este 4: (1, 2), (1, 5), (5, 8), (6, 1).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?