all-you-can-code-2008/treesearch

Tree Search

h2(#treesearch). 'Tree Search':problema/treesearch

...

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