Tree Search

Problema se rezolva prin programare dinamica. Presupunem ca agatam arborele intr-un nod oarecare. Folosind DFS, calculam P[ i ] = costul maxim al unui drum care contine drept capat nodul i, si contine doar noduri din subarborele lui i. Relatia de recurenta se determina relativ simplu: P[ i ] = C[ i ], daca i este nod terminal, iar P[ i ] = max ( C[ i ], C[ i ] + P[ k ] ), pentru k - adiacent a lui i ( diferit de tatal lui i ). De asemenea, mai trebuie calculat si un vector de tati: tata[ x ] = tatal nodului x. Avand acesti vectori calculati, mai trebuie sa determinam drumul de cost maxim care are drept extremitate nodul i, si pleaca "in sus". Astfel, notam cu T[ i ] - costul maxim al unui drum care pleaca din i, "in sus". Pentru a calcula acest vector, ne trebuie cate o parcurgere DF pt fiecare fiu al radacinii. Presupunem ca dorim sa calculam T[] pentru subarborele k al radacinii (asadar, k este fiu al radacinii). Trebuie sa procedam astfel:

  • 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]. Continuam parcurgerea cu fiecare subarbore a lui x (considerand radacina tot nodul radacina)

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).