QOJ.ac

QOJ

时间限制: 2 s 内存限制: 512 MB 总分: 100 可 Hack ✓

#21438. Another Story END

统计

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.