QOJ.ac

QOJ

Süre Sınırı: 2 s Bellek Sınırı: 512 MB Toplam puan: 100 Hack'lenebilir ✓

#21438. Another Story END

İstatistikler

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

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.