… Hva mer kan man ønske seg enn en lykkelig slutt?
Du får gitt et tre med $n$ noder nummerert fra $1$ til $n$, med rot i node $1$. For hver $i = 2, 3, \ldots, n$ er det en toveis kant mellom node $i$ og forelderen $p_i$ med farge $c_i$ og lengde $w_i$.
For en farge $c$ som forekommer i treet, hvis en enkel sti går gjennom alle kanter med farge $c$, eller ikke går gjennom noen kant med farge $c$, sier vi at fargen $c$ er god for denne stien; ellers sier vi at fargen $c$ er dårlig for denne stien.
Gitt et heltall $k \in \{0, 1\}$, finn den maksimale lengden på en enkel sti med høyst $k$ dårlige farger. Lengden på en sti er definert som summen av lengdene til alle kantene på stien.
Du kan velge samme node som begge endepunktene til stien; i så fall går stien ikke gjennom noen kanter og har lengde $0$.
Merk at kanter med samme farge ikke nødvendigvis er sammenhengende, og at lengden på en kant kan være $0$.
Inndata
Den første linjen inneholder to heltall $n, k$, som representerer henholdsvis antall noder og øvre grense for antall tillatte dårlige farger.
Den $i$-te av de neste $n - 1$ linjene inneholder tre heltall $p_i, c_i, w_i$, som angir at det er en toveis kant mellom node $i$ og node $p_i$ med farge $c_i$ og lengde $w_i$.
Utdata
Skriv ut én linje med ett heltall, som representerer den maksimale lengden på en enkel sti med høyst $k$ dårlige farger.
Eksempler
Inndata 1
6 1 1 1 1 1 1 4 1 2 2 1 2 8 1 3 100
Utdata 1
108
Forklaring
Velg stien fra node $5$ til node $6$, som går gjennom nodene $5, 1, 6$ i rekkefølge, med lengde $8 + 100 = 108$.
Denne stien går ikke gjennom noen kant med farge $1$ og går gjennom alle kanter med farge $3$, så fargene $1, 3$ er begge gode. Den går bare gjennom én av de to kantene med farge $2$, så farge $2$ er dårlig.
Denne stien har nøyaktig én dårlig farge, noe som oppfyller kravet. Det kan bevises at det ikke finnes noen lengre gyldig sti.
Inndata 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
Utdata 2
35
Forklaring
Velg stien fra node $8$ til node $9$, som går gjennom nodene $8, 4, 2, 1, 3, 6, 9$ i rekkefølge, med lengde $8 + 5 + 3 + 4 + 6 + 9 = 35$.
Denne stien går gjennom alle kanter med fargene $1, 2, 5$ og ingen kanter med fargene $3, 4$, så den har ingen dårlige farger og oppfyller kravet. Det kan bevises at det ikke finnes noen lengre gyldig sti.
Inndata 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
Utdata 3
16
Forklaring
Velg stien fra node $7$ til node $8$, som går gjennom nodene $7, 2, 1, 3, 8$ i rekkefølge, med lengde $2 + 6 + 5 + 3 = 16$.
Denne stien går gjennom to av de tre kantene med farge $1$, så farge $1$ er dårlig. Den går gjennom alle kanter med fargene $3, 4$ og ingen kanter med andre farger, så den har nøyaktig én dårlig farge og oppfyller kravet.
Stien fra node $7$ til node $9$ har lengde $17$, men fargene $1, 2$ er begge dårlige, så den oppfyller ikke kravet. Det kan bevises at det ikke finnes noen gyldig sti med lengde større enn $16$.
Begrensninger
For alle testdata gjelder:
- $2 \le n \le 2 \times 10^5$;
- $k \in \{0, 1\}$;
- For hver $i = 2, 3, \ldots, n$ er $1 \le p_i < i$, $1 \le c_i \le n$ og $0 \le w_i \le 10^9$.
Deloppgaver
Denne oppgaven bruker gruppert testing med rimelige avhengigheter mellom deloppgavene.
| Deloppgave | $n \le$ | $k =$ | Spesiell egenskap | Poeng |
|---|---|---|---|---|
| $1$ | $200$ | $0$ eller $1$ | Ingen | $5$ |
| $2$ | $3000$ | $0$ eller $1$ | Ingen | $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$ | Ingen | $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$ | Ingen | $11$ |
| $13$ | $2 \times 10^5$ | $1$ | Ingen | $13$ |
- Spesiell egenskap A: For hver farge danner alle kanter av denne fargen en sammenhengende delgraf.
- Spesiell egenskap B: Hver farge forekommer høyst to ganger.
- Spesiell egenskap C: For hver $i = 2, 3, \ldots, n$ velges $p_i$ uavhengig og uniformt tilfeldig blant heltallene $1, 2, \ldots, i - 1$.
- Spesiell egenskap D: For hver farge finnes det en enkel sti med node $1$ som ett av endepunktene som inneholder alle kanter av denne fargen.