Fişierul intrare/ieşire:brazi.in, brazi.outSursăONIS 2014, Runda 1
AutorCazacu AlexandruAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test3 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Brazi

Anul acesta brazii au forma unor arbori binar. Un brad este identificat prin numarul de noduri N si N-1 muchii care pot fi de doua tipuri:

  • x y 0 insemnand ca y este fiul stang al lui x
  • x y 1 insemnand ca y este fiul drept al lui x

Doi brazi sunt asemenea daca, schimband etichetarea unuia dintre ei, se obtin fix muchiile celuilalt.

De exemplu: bradul 1 2 0, 1 3 1, 2 4 0 nu este asemenea cu bradul 1 2 1, 1 3 0, 2 4 1 dar este asemenea cu 1 3 0, 1 2 1, 3 4 0.

Se dau T astfel de brazi care contin maxim 10 noduri. Pentru fiecare brad i, sa se afiseze numarul de brazi din primii i-1 care sunt asemenea cu el. 

Date de intrare

Fişierul de intrare brazi.in contine pe prima linie un numar natural T, numarul de brazi. Fiecare brad este descris in N linii. Pe prima se afla N, numarul de noduri. Pe urmatoarele N-1 se afla 3 numere x y 0 sau x y 1 reprezentand o muchie a bradului.

Date de ieşire

În fişierul de ieşire brazi.out va contine T linii. Pe linia i se va scrie numarul de brazi din primii i-1 care sunt asemenea cu bradul i.

Restricţii

  • 1 ≤ T ≤ 100000
  • 1 ≤ N ≤ 10
  • 1 ≤ x, y ≤ N

Exemplu

brazi.inbrazi.out
3
4
1 2 0
1 3 1
2 4 0
4
1 2 1
1 3 0
2 4 1
4
1 3 0
1 2 1
3 4 0
0
0
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content