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ă 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.

h2. Date de intrare