Arbore3

Vom calcula pentru nodurile arborelui un vector Sum, unde Sum[nod] va fi egal cu valoarea sumei tuturor nodurilor de pe drumul de la nod la radacina. Suma pentru un drum in arbore de la un nod A la un stramos de-al sau B va fi egala cu Sum[A] - Sum[Tata[B]]. Efectuand o parcurgere in adancime a arborelui, ne intereseaza pentru fiecare nod cati stramosi are atfel incat Sum[Tata[stramos]] = Sum[nod] - S. Pentru a raspunde eficient la aceaste interogari, vom mentine o tabela hash pentru elemente ale vectorului Sum, in care vom insera valori cand vom inainta in parcuregerea subarborelui si vom scoate valori cand ne intoarcem din subarbore. Interogarile se reduc la a determina cate elemente cu o anumita valoare exista in tabela hash.