Se numeşte arbore cu rădăcină o structură care conţine un nod special denumit rădăcina arborelui şi A1, A2, ..., An (unde n≥0) arbori cu rădăcină (denumiţi subarbori ai rădăcinii). Nodul rădăcină al fiecărui arbore Ai este denumit fiu al rădăcinii arborelui şi este conectat printr-o muchie de rădăcina arborelui.
Doi arbori cu rădăcină sunt identici dacă rădăcinile celor doi au acelaşi număr de subarbori şi aceştia 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 termită poate „ciopli” un arbore acţionând astfel:
1) termita porneşte de la rădăcina arborelui;
2) la fiecare moment (în orice nod s-ar afla), termita poate face una dintre următoarele operaţii:
– stă în nod şi mănâncă cea mai din dreapta muchie, eliminând astfel cel mai din dreapta fiu şi subarborele corespunzător (acestea cad şi vor fi mâncate de alte termite leneşe);
– înaintează pe muchia din dreapta, spre fiul rămas cel mai din dreapta al nodului în care se află;
– se opreşte.
Două termite prietene aleg doi arbori şi îi cioplesc în modul descris până când obţin doi arbori identici. Similaritatea dintre doi arbori este egală cu numărul maxim de noduri care rămân în fiecare dintre cei doi arbori identici obţinuţi prin cioplire.
Cerinţă
Dându-se doi arbori (un arbore model şi un arbore de evaluat) să se calculeze pentru fiecare nod al arborelui de evaluat similaritatea dintre subarborele cu rădăcina în nodul respectiv şi arborele model dat.
Date de intrare
Pe prima linie a fişierului de intrare arbfind.in se găseşte un număr natural N reprezentând numărul 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 număr natural Fi-1 reprezentând numărul de fii direcţi ai nodului i-1, urmat de Fi-1 numere naturale cuprinse între 1 şi N, reprezentând în ordinea de la stânga la dreapta fiii nodului i-1.
Linia N+2 va conţine un număr natural M reprezentând numărul de noduri din arborele de evaluat. Liniile N+3..N+M+2 vor conţine descrierea arborelui de evaluat, în mod analog cu descrierea arborelui model.
Date de ieşire
Fişierul de ieşire arbfind.out va conţine M linii. Pe linia i se va afla similaritatea subarborelui cu rădăcina în nodul i faţă de arborele model.
Restricţii
Rădăcina arborilor este întotdeauna nodul 1.
1 ≤ M, N ≤ 16000
De exemplu, pentru nodul 1 din arborele model s-au eliminat în ordine subarborii cu rădăcinile 3, 5 şi 8. Din arborele model se elimină subarborele cu rădăcina 3.
