Subarbore

Observăm că numărul de noduri speciale T este foarte mic, deci problema admite o soluţie exponenţială. Vom construi următoarea dinamică: D[i][j] = dimensiunea minimă a unui subarbore care conţine nodurile speciale corespunzătoare biţilor de 1 din configuraţia binară a lui i, şi are rădăcina în nodul j. Avem două metode prin care putem construi un astfel de subarbore:

1. Unim doi subarbori mai mici care au rădăcina în acelaşi nod j şi acoperă două mulţimi disjuncte de noduri speciale.
2. Având un subarbore cu rădăcina în alt nod x, adăugăm un lanţ de la nodul j la nodul x.

Astfel, recurenţa noastră devine:

D[i][j] = minim din:

• D[i₁][j] + D[i₂][j], unde i₁ or i₂ = i (submulţimile i₁ şi i₂ reunite dau submulţimea i) şi i₁ and i₂ = 0 (submulţimile sunt disjuncte). Submulţimile pot fi găsite de exemplu, găsind mai întâi pe i₁ astfel încât să fie o submulţime a lui i, iar apoi aflăm pe i₂ = i - i₁;
• D[i][x] + Dist[j][x], unde în matricea Dist avem precalculate distanţele între oricare două noduri din arbore. Această precalculare poate fi făcută aplicând algoritmul Roy-Floyd.

Este important ca, pentru orice stare i, să calculăm întâi dinamica pentru toate rădăcinile j bazându-ne pe prima parte a recurenţei (unirea a doi arbori) şi abia apoi pe a doua (prelungirea unui lanţ) deoarece rezultatele celei de-a doua recurenţe depind de cele obţinute din prima.

Complexitate: O(3^T*N + 2^T*N²) timp şi O(2^T*N) memorie.