Se dă un arbore cu $N$ noduri numerotate de la $1$ la $N$ cu rădăcina în nodul $1$. Fiecare muchie are asociat un cost. Pentru a ajunge din nodul $1$ într-un nod $D$, se izolează lanţul dintre nodul $1$ şi nodul $D$ de restul arborelui, apoi se parcurg pe acest lanţ pornind din nodul $1$ muchii în jos sau în sus, respectând restricţiile puse pe noduri, până când se ajunge în nodul $D$. Definim o restricţie pusă pe un nod $X$ ca fiind un alt nod $Y$, care este strămoş al nodului $X$, cu semnificaţia că nu putem intra în nodul $X$ dacă nodul $Y$ se află printre ultimele $K$ noduri vizitate. La fiecare trecere printr-o muchie, se adaugă la costul parcurgerii costul asociat acelei muchii.

Să se afle pentru fiecare nod $i$, $1 ≤ i ≤ N$,  în parte, care este costul minim de a ajunge din nodul $1$ în nodul $i$, respectând restricţiile puse pe noduri, ştiind că pe drumul de la rădăcină la nodul $i$ este prioritară minimizarea costului de a ajunge pe primul nivel, apoi pe al doilea etc.

Să se afle pentru fiecare nod $i$, $1 ≤ i ≤ N$,  în parte, care este costul minim de a ajunge din nodul $1$ în nodul $i$, respectând restricţiile puse pe noduri, *ştiind că dacă o muchie a fost parcursă de $H$ ori pe drumul de cost minim de la rădăcină la un nod $X$, atunci aceasta trebuie parcursă de cel puţin $H$ ori şi pe drumul de cost minim de la rădăcină la orice fiu direct sau indirect al nodului $X$*.

h2. Date de intrare

21
144
11

-1

-1 |
| 6 5
1 3 -1
2 1 -1
3 2 -1
4 3 1
5 3 2
| 0
3
4
6
11
18

|
h3. Explicaţie

Pentru a ajunge din rădăcină în nodul $5$ cu un cost minim vom parcurge următorul traseu: $1 -> 3 -> 2 -> 3 -> 2 -> 5$, costul fiind $1 + 2 + 2 + 2 + 3 = 10$. Restricţia pusă asupra nodului $5$ nu ne lasă să intrăm în acest nod dacă nodul $1$ se află printre ultimele $3$ noduri vizitate. De aceea, din nodul $2$ mergem înapoi în nodul $3$ şi apoi coborâm până în nodul $5$. Astfel, ultimele $3$ noduri prin care trecem înainte de a intra în nodul $5$ sunt $2, 3, 2$.
Nu se poate ajunge din rădăcină în nodul $6$, deoarece restricţia pusă pe nodul $6$ nu ne lasă să intrăm în acest nod dacă nodul $1$ se află printre ultimele $3$ noduri vizitate. Costul minim pentru acest nod este $-1$.

În al treilea exemplu, se poate ajunge în nodul $6$, respectând restricţiile puse pe noduri, şi cu un cost de $16$, dar asta ar însemna să nu parcurgem muchia $(2,3)$ de cel puţin $3$ ori (muchia a fost parcursă de $3$ ori pentru a ajunge din nodul $1$ în nodul $5$, iar nodul $6$ este un fiu direct al nodului $5$).
 

== include(page="template/taskfooter" task_id="restrict") ==