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:
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$]$.
* 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).
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$).
