QOJ.ac

QOJ

Límite de tiempo: 2 s Límite de memoria: 512 MB Puntuación total: 100 Hackeable ✓

#21438. Another Story END

Estadísticas

… Mitä muuta voisit vielä toivoa kuin onnellisen lopun?

Annettuna on puu, jossa on $n$ solmua numeroituna $1$:stä $n$:ään ja jonka juuri on solmu $1$. Jokaiselle $i = 2, 3, \ldots, n$ solmun $i$ ja sen vanhemman $p_i$ välillä on kaksisuuntainen kaari, jonka väri on $c_i$ ja pituus $w_i$.

Puussa esiintyvälle värille $c$ sanotaan, että väri $c$ on hyvä yksinkertaiselle polulle, jos polku kulkee kaikkien värin $c$ kaarien kautta tai ei kulje minkään värin $c$ kaaren kautta; muulloin väri $c$ on huono tälle polulle.

Annettuna on kokonaisluku $k \in \{0, 1\}$. Etsi sellaisen yksinkertaisen polun suurin mahdollinen pituus, jolla on enintään $k$ huonoa väriä. Polun pituus määritellään polulla olevien kaarien pituuksien summana.

Voit valita saman solmun polun molemmiksi päätepisteiksi; tällöin polku ei kulje minkään kaaren kautta ja sen pituus on $0$.

Huomaa, että samanväristen kaarien ei tarvitse muodostaa yhtenäistä aliverkkoa ja että kaaren pituus voi olla $0$.

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua $n, k$, jotka ilmoittavat solmujen lukumäärän ja huonojen värien suurimman sallitun määrän.

Seuraavien $n - 1$ rivin $i$-nnellä rivillä on kolme kokonaislukua $p_i, c_i, w_i$, jotka kertovat, että solmun $i$ ja solmun $p_i$ välillä on kaksisuuntainen kaari, jonka väri on $c_i$ ja pituus $w_i$.

Tuloste

Tulosta yksi rivi, jolla on yksi kokonaisluku: sellaisen yksinkertaisen polun suurin pituus, jolla on enintään $k$ huonoa väriä.

Esimerkit

Syöte 1

6 1
1 1 1
1 1 4
1 2 2
1 2 8
1 3 100

Tuloste 1

108

Huomautus

Valitaan polku solmusta $5$ solmuun $6$, joka kulkee järjestyksessä solmujen $5, 1, 6$ kautta ja jonka pituus on $8 + 100 = 108$.

Tämä polku ei kulje minkään värin $1$ kaaren kautta ja kulkee kaikkien värin $3$ kaarien kautta, joten värit $1, 3$ ovat molemmat hyviä. Se kulkee vain yhden värin $2$ kahdesta kaaresta kautta, joten väri $2$ on huono.

Tällä polulla on täsmälleen yksi huono väri, joten se täyttää ehdon. Voidaan todistaa, ettei pidempää kelvollista polkua ole olemassa.

Syöte 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

Tuloste 2

35

Huomautus

Valitaan polku solmusta $8$ solmuun $9$, joka kulkee järjestyksessä solmujen $8, 4, 2, 1, 3, 6, 9$ kautta ja jonka pituus on $8 + 5 + 3 + 4 + 6 + 9 = 35$.

Tämä polku kulkee kaikkien värien $1, 2, 5$ kaarien kautta eikä minkään värien $3, 4$ kaaren kautta, joten huonoja värejä ei ole ja ehto täyttyy. Voidaan todistaa, ettei pidempää kelvollista polkua ole olemassa.

Syöte 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

Tuloste 3

16

Huomautus

Valitaan polku solmusta $7$ solmuun $8$, joka kulkee järjestyksessä solmujen $7, 2, 1, 3, 8$ kautta ja jonka pituus on $2 + 6 + 5 + 3 = 16$.

Tämä polku kulkee kahden värin $1$ kolmesta kaaresta kautta, joten väri $1$ on huono. Se kulkee kaikkien värien $3, 4$ kaarien kautta eikä minkään muun värin kaaren kautta, joten sillä on täsmälleen yksi huono väri ja se täyttää ehdon.

Polun solmusta $7$ solmuun $9$ pituus on $17$, mutta värit $1, 2$ ovat molemmat huonoja, joten ehto ei täyty. Voidaan todistaa, ettei yli pituuden $16$ kelvollista polkua ole olemassa.

Rajoitukset

Kaikissa testiaineistoissa pätee:

  • $2 \le n \le 2 \times 10^5$;
  • $k \in \{0, 1\}$;
  • Jokaiselle $i = 2, 3, \ldots, n$ pätee $1 \le p_i < i$, $1 \le c_i \le n$ ja $0 \le w_i \le 10^9$.

Osatehtävät

Tässä tehtävässä käytetään ryhmiteltyä testausta ja osatehtävien välillä on järkevät riippuvuudet.

Osatehtävä $n \le$ $k =$ Erikoisominaisuus Pisteet
$1$ $200$ $0$ tai $1$ Ei ole $5$
$2$ $3000$ $0$ tai $1$ Ei ole $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$ Ei ole $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$ Ei ole $11$
$13$ $2 \times 10^5$ $1$ Ei ole $13$
  • Erikoisominaisuus A: Jokaiselle värille kaikki kyseisen värin kaaret muodostavat yhtenäisen aliverkon.
  • Erikoisominaisuus B: Jokainen väri esiintyy enintään kaksi kertaa.
  • Erikoisominaisuus C: Jokaiselle $i = 2, 3, \ldots, n$ luku $p_i$ valitaan riippumattomasti ja tasatodennäköisesti kokonaislukujen $1, 2, \ldots, i - 1$ joukosta.
  • Erikoisominaisuus D: Jokaiselle värille on olemassa yksinkertainen polku, jonka toinen päätepiste on solmu $1$ ja joka sisältää kaikki kyseisen värin kaaret.

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.