h3. (problema grea, clasa a 10-a, problema medie, clasele 11-12)

Observam ca algoritmul de parcurgere al lui Bob reprezinta de fapt parcurgerea Euler a arborelui. Singura diferenta este consta in faptul ca el nu noteaza nodurile prin care trece, ci doar culorile acestora.
 
Fie un arbore cu radacina in $T$, aceasta avand fii $F{~1~}$, $F{~2~}$, ... $F{~k~}$. Notand cu $[T]$ vectorul de culori generat de arborele de radacina $T$, obtinem $[T] = T$, daca arborele contine un singur nod si $[T] = T + [F{~1~}] + T + [F{~2~}] ... [F{~k~}] + T$ altfel (unde $"+"$ este operatorul de concatenare).
 
De aici se contureaza repede ideea de programare dinamica. Construim matricea $A{~i,j~} = numarul de arbori care ar fi putut genera subsecventa i..j a sirului initial de culori$.
 
Din constructia sirului de culori reiese ca are sens sa calculam $A{~i,j~}$ numai daca $C{~i~} = C{~j~}$ (unde $C$ este vectorul de culori). In acest caz subarborele determinat de primul fiu al radacinii curente va genera sirul de culori cuprins $i+1$ si un indice $k$. Fixandu-l pe acesta, problema se reduce la numararea posibilitatilor de a forma arbori care sa corespunda intervalului $i+1..k$ si cea de a forma arbori pentru intervalul $k+1..j$
 
Astfel avem $A{~i,i~} = 1$ si $A{~i,j~} = Suma(A{~i+1,k~} * A{~k+1,j~} | i < k < j si C{~i+1~} = C{~k~})$.
 
Complexitatea algoritmului este $O(N^3^)$, dar daca este implementat cu grija poate fi facut sa ruleze in aprox. 0.5 secunde pentru oricare din testele folosite la evaluare. O ultima optimizare (mica, dar care imbunatateste codul in mod simtitor) consta in faptul ca, deoarece orice parcurgere euler este de lungime impara, are rost sa calculam $A{~i,j~}$ numai daca $i+j$ este numar par.
 

h2. 'Reguli':problema/reguli
h3. (problema usoara, clasele 11-12)