QOJ.ac

QOJ

実行時間制限: 2 s メモリ制限: 512 MB 満点: 100 ハック可能 ✓

#21438. Another Story END

統計

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

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.