* T[$radacina$] se initializeaza cu max ( C[$radacina$], P[$j$] ), unde $j$ este un fiu al radacinii, diferit de $k$.
* Aplicam un algoritm de tip DF, avand ca punct de plecare $k$. Pentru fiecare nod x pe care il parcurgem (avand tatal t) calculam T[$x$] = max ( C[$x$], C[$x$] + T[$t$], C[$x$] + C[$t$] + P[$j$]), unde $j$ este un fiu al lui $t$, diferit de $i$ si diferit de $tata[$t$]$.

Asadar, putem acum calcula $bst[$x$]$ = costul maxim al unui drum care contine nodul $x$, pe baza lui $P$ si a lui $T$. Relatia de recurenta se determina usor. Avand acest vector calculat, putem raspunde in O(1) pe query. Asadar complexitatea programului va fi O(N+M).

Asadar, putem acum calcula $bst[$x$]$ = costul maxim al unui drum care contine nodul $x$, pe baza lui $P$ si a lui $T$. Relatia de recurenta se determina usor. Avand acest vector calculat, putem raspunde in O(1) pe query. Asadar complexitatea programului va fi O($N$+$M$).

Observatie: Pentru a calcula cel mai mare fiu al radacinii, diferit de fiul $k$, se va folosi un deque, altfel algoritmul putand deveni O($N^2$), in caz contrar.

Observatie: Pentru a calcula cel mai mare fiu al radacinii, diferit de fiul $k$, se va folosi un deque, altfel algoritmul putand deveni O($N$^$2$), in caz contrar.