Fişierul intrare/ieşire:arbfind.in, arbfind.outSursăLot 2006
AutorEmilian MironAdăugată de
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Arbfind

Se numeste arbore cu radacina o structura care contine un nod special denumit radacina arborelui si A1, A2, ..., An (unde n ≥ 0) arbori cu radacina (denumiti subarbori ai radacinii). Nodul radacina al fiecarui arbore Ai este denumit fiu al radacinii arborelui si este conectat printr-o muchie de radacina arborelui.

Doi arbori cu radacina sunt identici daca radacinile celor doi au acelasi numar de subarbori si acestia sunt identici (mai exact, pentru orice i=1, 2, ..., n subarborele i al primului este identic cu subarborele i al celui de-al doilea).

O termita poate "ciopli" un arbore actionand astfel:
1. termita porneste de la radacina arborelui;
2. la fiecare moment (in orice nod s-ar afla), termita poate face una dintre urmatoarele operatii:

  • sta in nod si mananca cea mai din dreapta muchie, eliminand astfel cel mai din dreapta fiu si subarborele corespunzator (acestea cad si vor fi mancate de alte termite lenese);
  • inainteaza pe muchia din dreapta, spre fiul ramas cel mai din dreapta al nodului in care se afla;
  • se opreste

Doua termite prietene aleg doi arbori si ii cioplesc in modul descris pana cand obtin doi arbori identici. Similaritatea dintre doi arbori este egala cu numarul maxim de noduri care raman in fiecare dintre cei doi arbori identici obtinuti prin cioplire.

Cerinta

Dandu-se doi arbori (un arbore model si un arbore de evaluat) sa se calculeze pentru fiecare nod al arborelui de evaluat similaritatea dintre subarborele cu radacina in nodul respectiv si arborele model dat.

Date de Intrare

Pe prima linie a fisierului de intrare arbfind.in se gaseste un numar natural N reprezentand numarul de noduri din arborele model, nodurile fiind numerotate de la 1 la N. Pe liniile 2..N+1 se va afla descrierea arborelui model. Mai exact, pe linia i se va afla un numar natural Fi-1 reprezentand numarul de fii directi ai nodului i-1, urmat de F i-1 numere naturale cuprinse intre 1 si N, reprezentand in ordinea de la stanga la dreapta fiii nodului i-1.

Linia N+2 va contine un numar natural M reprezentand numarul de noduri din arborele de evaluat. Liniile N+3..N+M+2 vor contine descrierea arborelui de evaluat, in mod analog cu descrierea arborelui model.

Date de Iesire

Fisierul de iesire arbfind.out va contine M linii. Pe linia i se va afla similaritatea subarborelui cu radacina in nodul i fata de arborele model.

Restrictii si precizari

  • Radacina arborilor este intotdeauna nodul 1.
  • 1 ≤ M, N ≤ 32000

Exemplu

arbfind.inarbfind.out
4
2 2 3
1 4
0
0
9
2 2 3
2 4 5
2 6 7
1 8
0
0
1 9
0
0
3
4
2
2
1
1
2
1
1

Explicatii

De exemplu, pentru nodul 1 din arborele model s-au eliminat in ordine subarborii cu radacinile 3, 5 si 8. Din arborele model se elimina subarborele cu radacina 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content