… Hvað annað gæti maður óskað sér en farsælan endi?
Gefið er tré með $n$ hnútum sem eru númeraðir frá $1$ til $n$, með rót í hnúti $1$. Fyrir hvert $i = 2, 3, \ldots, n$ er tvístefndur leggur á milli hnúts $i$ og foreldris hans $p_i$ með lit $c_i$ og lengd $w_i$.
Fyrir lit $c$ sem kemur fyrir í trénu, ef einfaldur vegur fer um alla leggi af lit $c$, eða fer ekki um neinn legg af lit $c$, þá segjum við að litur $c$ sé góður fyrir þennan veg; annars segjum við að litur $c$ sé slæmur fyrir þennan veg.
Gefin er heiltala $k \in \{0, 1\}$. Finndu mestu lengd einfalds vegar sem hefur í mesta lagi $k$ slæma liti. Lengd vegar er skilgreind sem summa lengda allra leggja á veginum.
Þú mátt velja sama hnút sem báða endapunkta vegarins; í því tilfelli fer vegurinn ekki um neina leggi og hefur lengdina $0$.
Athugið að leggir af sama lit eru ekki endilega samanhangandi og lengd leggs getur verið $0$.
Inntak
Fyrsta línan inniheldur tvær heiltölur $n, k$, sem tákna fjölda hnúta og hámarksfjölda leyfilegra slæmra lita.
$i$-ta línan af næstu $n - 1$ línum inniheldur þrjár heiltölur $p_i, c_i, w_i$, sem gefa til kynna að tvístefndur leggur sé á milli hnúts $i$ og hnúts $p_i$ með lit $c_i$ og lengd $w_i$.
Úttak
Skrifið út eina línu með einni heiltölu sem táknar mestu lengd einfalds vegar með í mesta lagi $k$ slæma liti.
Dæmi
Inntak 1
6 1 1 1 1 1 1 4 1 2 2 1 2 8 1 3 100
Úttak 1
108
Skýring
Veljum veginn frá hnúti $5$ til hnúts $6$, sem fer í röð um hnúta $5, 1, 6$, með lengd $8 + 100 = 108$.
Þessi vegur fer ekki um neinn legg af lit $1$ og fer um alla leggi af lit $3$, þannig að litir $1, 3$ eru báðir góðir. Hann fer aðeins um annan af tveimur leggjum af lit $2$, þannig að litur $2$ er slæmur.
Þessi vegur hefur nákvæmlega einn slæman lit og uppfyllir því skilyrðið. Sanna má að enginn lengri gildur vegur sé til.
Inntak 2
10 0 1 1 3 1 2 4 2 1 5 2 3 40 3 2 6 3 4 2 4 5 8 6 5 9 7 3 10
Úttak 2
35
Skýring
Veljum veginn frá hnúti $8$ til hnúts $9$, sem fer í röð um hnúta $8, 4, 2, 1, 3, 6, 9$, með lengd $8 + 5 + 3 + 4 + 6 + 9 = 35$.
Þessi vegur fer um alla leggi af litum $1, 2, 5$ og enga leggi af litum $3, 4$, þannig að hann hefur enga slæma liti og uppfyllir skilyrðið. Sanna má að enginn lengri gildur vegur sé til.
Inntak 3
10 1 1 1 6 1 1 5 1 1 0 1 2 8 1 2 0 2 3 2 3 4 3 5 5 1 6 6 4
Úttak 3
16
Skýring
Veljum veginn frá hnúti $7$ til hnúts $8$, sem fer í röð um hnúta $7, 2, 1, 3, 8$, með lengd $2 + 6 + 5 + 3 = 16$.
Þessi vegur fer um tvo af þremur leggjum af lit $1$, þannig að litur $1$ er slæmur. Hann fer um alla leggi af litum $3, 4$ og enga leggi af öðrum litum, þannig að hann hefur nákvæmlega einn slæman lit og uppfyllir skilyrðið.
Vegurinn frá hnúti $7$ til hnúts $9$ hefur lengdina $17$, en litir $1, 2$ eru báðir slæmir, svo hann uppfyllir ekki skilyrðið. Sanna má að enginn gildur vegur með lengd meiri en $16$ sé til.
Takmarkanir
Fyrir öll prófunargögn gildir:
- $2 \le n \le 2 \times 10^5$;
- $k \in \{0, 1\}$;
- Fyrir hvert $i = 2, 3, \ldots, n$ gildir $1 \le p_i < i$, $1 \le c_i \le n$ og $0 \le w_i \le 10^9$.
Undirverkefni
Þetta verkefni notar hópaprófun (bundled testing) með eðlilegum háðum milli undirverkefna.
| Undirverkefni | $n \le$ | $k =$ | Sérstakur eiginleiki | Stig |
|---|---|---|---|---|
| $1$ | $200$ | $0$ eða $1$ | Enginn | $5$ |
| $2$ | $3000$ | $0$ eða $1$ | Enginn | $9$ |
| $3$ | $2 \times 10^5$ | $0$ | A | $4$ |
| $4$ | $2 \times 10^5$ | $0$ | B | $5$ |
| $5$ | $2 \times 10^5$ | $0$ | C | $3$ |
| $6$ | $2 \times 10^5$ | $0$ | D | $4$ |
| $7$ | $2 \times 10^5$ | $0$ | Enginn | $7$ |
| $8$ | $2 \times 10^5$ | $1$ | A | $8$ |
| $9$ | $2 \times 10^5$ | $1$ | B | $14$ |
| $10$ | $2 \times 10^5$ | $1$ | C | $9$ |
| $11$ | $2 \times 10^5$ | $1$ | D | $8$ |
| $12$ | $10^5$ | $1$ | Enginn | $11$ |
| $13$ | $2 \times 10^5$ | $1$ | Enginn | $13$ |
- Sérstakur eiginleiki A: Fyrir hvern lit mynda allir leggir af þeim lit samanhangandi hlutnet.
- Sérstakur eiginleiki B: Hver litur kemur fyrir í mesta lagi tvisvar.
- Sérstakur eiginleiki C: Fyrir hvert $i = 2, 3, \ldots, n$ er $p_i$ valið óháð og af handahófi með jöfnum líkum úr heiltölunum $1, 2, \ldots, i - 1$.
- Sérstakur eiginleiki D: Fyrir hvern lit er til einfaldur vegur með hnút $1$ sem annan endapunkt sinn sem inniheldur alla leggi af þeim lit.