== include(page="template/taskheader" task_id="restrict") ==
Poveste şi cerinţă...
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ă 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
Fişierul de intrare $restrict.in$ ...
Fişierul de intrare $restrict.in$ conţine pe prima linie două numere întregi $N$ şi $K$, cu semnificaţia din enunţ. Următoarele $N-1$ linii conţin câte $3$ numere întregi fiecare. A $i$-a linie dintre aceste $N-1$ linii conţine următoarele $3$ valori: primul număr reprezintă părintele nodului $i+1$, al doilea număr reprezintă costul muchiei dintre nodul $i+1$ şi părintele acestuia, al treilea număr reprezintă restricţia pusă pe nodul $i+1$, această valoare este egală cu $-1$ dacă pe nodul $i+1$ nu este pusă nicio restricţie.
h2. Date de ieşire
În fişierul de ieşire $restrict.out$ ...
Fişierul de ieşire $restrict.out$ trebuie să conţină $N$ linii, fiecare conţinând o singură valoare, a $i$-a valoare reprezentând costul minim de a ajunge din rădăcină în nodul $i$ sau $-1$ în cazul în care nu se poate ajunge în acest nod.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $0 ≤ N, K ≤ 100 000$
* $0 ≤ costul unei muchii ≤ 1 000 000$
* 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.
* Exemplele vor reprezenta teste în valoare de $10$ puncte "din oficiu".
h2. Exemplu
table(example). |_. restrict.in |_. restrict.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 6 3
3 2 -1
1 1 -1
1 8 -1
2 3 1
1 4 1
| 0
3
1
8
10
-1 |
| 14 6
10 20 -1
7 1 5
10 2 1
1 7 -1
9 7 11
8 0 -1
4 7 13
2 11 -1
11 3 -1
13 10 -1
3 100 -1
5 4 -1
2 165 2
| 0
44
44
32
7
106
43
43
55
24
21
144
11
-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 primul exemplu avem arborele:
!problema/restrict?restrict.png!
Pentru a ajunge din rădăcină în nodul $1$ se observă că nu trebuie să facem nicio mutare, deci costul minim este $0$.
Pentru a ajunge din rădăcină în nodul $2$ cu un cost minim vom parcurge următorul traseu: $1 -> 3 -> 2$, costul fiind $1 + 2 = 3$.
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ă 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") ==
