Revizia anterioară Revizia următoare
Tree Search
Problema se rezolva prin programare dinamica. Presupunem ca agatam arborele intr-un nod oarecare. Folosind DFS, calculam Pi = 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: Pi = Ci, daca i este nod terminal, iar Pi = max ( Ci, Ci + Pk ), 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 Ti - 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:
- Tradacina se initializeaza cu max ( Cradacina, Pj ), 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 Tx = max ( Cx, Cx + Tt, Cx + Ct + Pj), 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$).
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.
