Subseqüències en camins d'un arbre X99792

Heu d’implementar un programa que llegirà un arbre d’enters t i també vàries seqüències d’enters. Per a cada seqüència s, el programa haurà de calcular quantes fulles hi ha a t tals que els elements de s es troben en el camí des de l’arrel fins a aquella fulla, en el mateix ordre, i a on possiblement hi pot haver també altres valors. Recordeu que una fulla és un arbre amb un únic node, i que per tant els seus dos fills directes són arbres buits.

Per exemple, considereu el següents arbre i seqüència:

Entrada:

5(1(,5(2(3, 1),3)),2(1,3(2,)))
1 2

Sortida:

2

En total hi ha 2 fulles tals que en el camí des de l’arrel fins a qualsevol d’aquelles fulles ens hi apareix la seqüència s (en el mateix ordre, i també enmig d’altres valors). Mostrem a continuació quins serien els 2 camins, que indiquem amb els valors dels nodes visitats:

5, 1, 5, 2, 3
5, 1, 5, 2, 1

Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: Makefile, BinaryTree.hpp. Us falta crear el fitxer program.cpp amb els corresponents includes i implementar-hi el programa que hem descrit. Quan pugeu la vostra solució al jutge, només cal que pugeu un tar construït així:

tar cf solution.tar program.cpp

Entrada

L’entrada té una primera línia amb un string que representa l’arbre t. Recordeu que podeu llegir l’string sobre una variable tstring i després usar readStringtree(tstring, t) per a transformar-lo en l’arbre t.

Cadascuna de les següents línies conté una seqüència d’enters. La podeu llegir i emmagatzemar com considereu convenient. Però penseu bé com ho feu (queue, stack, list, vector), doncs hi haurà maneres que faran més fàcil implementar un programa eficient.

Sortida

Per a cadascuna de les seqüències hi ha un valor de sortida en una línia, el nombre de fulles de t que cumpleixen la condició abans esmentada.

Observació

Aquest exercici requereix d’una bona optimització per tal de superar els jocs de proves privats.