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

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.

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

* Pentru teste în valoare de $10$ puncte, se garantează că $1 ≤ N ≤ 1 000$,  arborele este un lanţ (fiecare nod are cel mult un fiu) şi restricţiile nu se intersectează (dacă restricţia pusă pe nodul $X$ este nodul $Y$, atunci toate nodurile dintre $X$ şi $Y$ sunt fără restricţii).
* Pentru alte teste în valoare de $30$ puncte, se garantează că $1 ≤ N ≤ 1 000$.
* Problema va fi evaluată pe teste în valoare de $90$ de puncte.

* Se vor acorda $10$ puncte din oficiu (ultimele $2$ teste sunt exemplele).

* Exemplele vor reprezenta teste în valoare de $10$ puncte "din oficiu".

h2. Exemplu

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 $3$ cu un cost minim vom parcurge următorul traseu: $1 -> 3$, costul fiind $1$.
Pentru a ajunge din rădăcină în nodul $4$ cu un cost minim vom parcurge următorul traseu: $1 -> 4$, costul fiind $8$.
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ă pentru 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$.

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") ==