Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-04-13 19:38:47.
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 vopseşte în negru şi invers, dacă avea culoarea neagră, o vopseşte în alb.
Din păcate pentru grădinarul Marian, cand a ajuns acasă era deja prea târziu, Marius finalizând de efectuat toate cele M operaţii. Îngrozit, Marian vrea să afle câte muchii mai au acum culoarea albă.

Cerinţă

Precizându-se operaţiile aplicate de Marius, 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 conţine pe prima linie două numere naturale N şi M, separate prin câte un spaţiu, reprezentând numărul de noduri ale arborelui deţinut de grădinarul Marian, respectiv numărul de operaţii efectuate de Marius. Pe următoarele N-1 linii se află câte o pereche de numere x y, separate prin câte un spaţiu, reprezentând faptul că în arbore există o muchie de la nodul x la nodul y. Pe următoarele M linii se află câte o pereche de numere a b, separate prin câte un spaţiu, cu proprietatea că toate muchiile de pe drumul care începe la nodul a şi se termina la nodul b îşi schimbă culoarea.

Date de ieşire

În fişierul de ieşire arbore5.out trebuie să existe pe prima linie un singur număr natural, reprezentând câte muchii au culoarea albă după efectuarea tuturor celor M operaţii.

Restricţii

  • 2 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 100.000
  • Operaţiile efectuate de Marius se execută in ordinea din fişierul 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 schimbă culoarea muchiilor dintre nodurile: (4, 2), (2, 1), (1, 5), toate acestea având acum culoarea neagră (ele fiind iniţial albe).
A doua operatie schimbă culoarea muchiilor dintre nodurile: (7, 5), (5, 1), (1, 2), (2, 3), astfel muchiile (7, 5) şi (2, 3) devin neagre (înaintea acestei operatii fiind albe), iar muchiile (5, 1) şi (1, 2) devin albe (ele fiind negre din cauza operaţiei precedente).
Astfel, după aplicarea celor doua operaţii, numărul 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?