== include(page="template/taskheader" task_id="arbfind") ==
==Include(page="template/taskheader" task_id="arbfind")==
Poveste ...
Se numeste arbore cu radacina o structura care contine un nod special denumit radacina arborelui si $A{~1~}, A{~2~}, ..., A{~n~}$ (unde $n ≥ 0$) arbori cu radacina (denumiti subarbori ai radacinii). Nodul radacina al fiecarui arbore $A{~i~}$ 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.
h2. 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.
h2. Date de Intrare
h2. Restrictii
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 $F{~i-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.
h2. Date de intrare
h2. 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.
h2. Date de iesire
h2. Restrictii si precizari
...
* Radacina arborilor este intotdeauna nodul $1$.
* $1 ≤ M, N ≤ 32000$
h2. Exemplu
| arbfind.in | arbfind.out |
| linia1
linia2
linia3
| linia1
linia2
table(example). |_. arbfind.in |_. arbfind.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
|
== include(page="template/taskfooter" task_id="arbfind") ==
h3. Explicatii
!problema/arbfind?arbfind.jpg!
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.
==Include(page="template/taskfooter" task_id="arbfind")==
