… Vad mer kan man önska sig än ett lyckligt slut?
Du får ett träd med $n$ noder numrerade från $1$ till $n$, med rot i nod $1$. För varje $i = 2, 3, \ldots, n$ finns en dubbelriktad kant mellan nod $i$ och dess förälder $p_i$ med färgen $c_i$ och längden $w_i$.
För en färg $c$ som förekommer i trädet gäller att om en enkel väg passerar genom alla kanter med färgen $c$, eller inte passerar genom någon kant med färgen $c$, så kallas färgen $c$ bra för denna väg; annars kallas färgen $c$ dålig för denna väg.
Givet ett heltal $k \in \{0, 1\}$, bestäm den maximala längden på en enkel väg med högst $k$ dåliga färger. Längden på en väg definieras som summan av längderna av alla kanter på vägen.
Du kan välja samma nod som båda ändpunkterna för vägen; i så fall passerar vägen inga kanter och har längden $0$.
Observera att kanter med samma färg inte nödvändigtvis är sammanhängande, och att en kants längd kan vara $0$.
Indata
Den första raden innehåller två heltal $n, k$, som representerar antalet noder respektive det maximalt tillåtna antalet dåliga färger.
Den $i$-te av de följande $n - 1$ raderna innehåller tre heltal $p_i, c_i, w_i$, vilket anger att det finns en dubbelriktad kant mellan nod $i$ och nod $p_i$ med färgen $c_i$ och längden $w_i$.
Utdata
Skriv ut en enda rad med ett heltal som representerar den maximala längden på en enkel väg med högst $k$ dåliga färger.
Exempel
Indata 1
6 1 1 1 1 1 1 4 1 2 2 1 2 8 1 3 100
Utdata 1
108
Förklaring
Välj vägen från nod $5$ till nod $6$, som passerar noderna $5, 1, 6$ i ordning, med längden $8 + 100 = 108$.
Denna väg passerar inga kanter med färg $1$ och alla kanter med färg $3$, så färgerna $1, 3$ är båda bra. Den passerar endast en av de två kanterna med färg $2$, så färg $2$ är dålig.
Denna väg har exakt en dålig färg, vilket uppfyller kravet. Det kan bevisas att det inte finns någon längre giltig väg.
Indata 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
Förklaring
Välj vägen från nod $8$ till nod $9$, som passerar noderna $8, 4, 2, 1, 3, 6, 9$ i ordning, med längden $8 + 5 + 3 + 4 + 6 + 9 = 35$.
Denna väg passerar alla kanter med färgerna $1, 2, 5$ och inga kanter med färgerna $3, 4$, så den har inga dåliga färger och uppfyller kravet. Det kan bevisas att det inte finns någon längre giltig väg.
Indata 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
Förklaring
Välj vägen från nod $7$ till nod $8$, som passerar noderna $7, 2, 1, 3, 8$ i ordning, med längden $2 + 6 + 5 + 3 = 16$.
Denna väg passerar två av de tre kanterna med färg $1$, så färg $1$ är dålig. Den passerar alla kanter med färgerna $3, 4$ och inga kanter med andra färger, så den har exakt en dålig färg och uppfyller kravet.
Vägen från nod $7$ till nod $9$ har längden $17$, men färgerna $1, 2$ är båda dåliga, vilket inte uppfyller kravet. Det kan bevisas att det inte finns någon giltig väg med längd större än $16$.
Begränsningar
För alla testdata gäller:
- $2 \le n \le 2 \times 10^5$;
- $k \in \{0, 1\}$;
- För varje $i = 2, 3, \ldots, n$ gäller $1 \le p_i < i$, $1 \le c_i \le n$ och $0 \le w_i \le 10^9$.
Deluppgifter
Detta problem använder grupperad testning med rimliga beroenden mellan deluppgifter.
| Deluppgift | $n \le$ | $k =$ | Särskild egenskap | Poäng |
|---|---|---|---|---|
| $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$ |
- Särskild egenskap A: För varje färg bildar alla kanter av denna färg en sammanhängande delgraf.
- Särskild egenskap B: Varje färg förekommer högst två gånger.
- Särskild egenskap C: För varje $i = 2, 3, \ldots, n$ väljs $p_i$ oberoende och likformigt slumpmässigt bland heltalen $1, 2, \ldots, i - 1$.
- Särskild egenskap D: För varje färg finns en enkel väg med nod $1$ som en ändpunkt som innehåller alla kanter av denna färg.