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