QOJ.ac

QOJ

时间限制: 2 s 内存限制: 512 MB 总分: 100 可 Hack ✓

#21438. Another Story END

统计

… Was könnte man sich außer einem glücklichen Ende noch wünschen?

Gegeben ist ein Baum mit $n$ Knoten, die von $1$ bis $n$ nummeriert sind, mit Knoten $1$ als Wurzel. Für jedes $i = 2, 3, \ldots, n$ gibt es eine ungerichtete Kante zwischen Knoten $i$ und seinem Elternknoten $p_i$ mit der Farbe $c_i$ und der Länge $w_i$.

Für eine im Baum vorkommende Farbe $c$ heißt die Farbe $c$ gut für einen einfachen Pfad, wenn dieser Pfad entweder alle Kanten der Farbe $c$ oder gar keine Kante der Farbe $c$ durchläuft; andernfalls heißt die Farbe $c$ schlecht für diesen Pfad.

Gegeben eine ganze Zahl $k \in \{0, 1\}$, bestimme die maximale Länge eines einfachen Pfades mit höchstens $k$ schlechten Farben. Die Länge eines Pfades ist definiert als die Summe der Längen aller Kanten auf dem Pfad.

Du kannst denselben Knoten als beide Endpunkte des Pfades wählen; in diesem Fall durchläuft der Pfad keine Kanten und hat die Länge $0$.

Bitte beachte, dass Kanten derselben Farbe nicht unbedingt zusammenhängend sind und die Länge einer Kante $0$ sein kann.

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n, k$, die die Anzahl der Knoten bzw. die maximal erlaubte Anzahl schlechter Farben angeben.

Die $i$-te der nächsten $n - 1$ Zeilen enthält drei ganze Zahlen $p_i, c_i, w_i$ und gibt an, dass zwischen Knoten $i$ und Knoten $p_i$ eine ungerichtete Kante mit der Farbe $c_i$ und der Länge $w_i$ verläuft.

Ausgabe

Gib eine einzige Zeile mit einer ganzen Zahl aus, die die maximale Länge eines einfachen Pfades mit höchstens $k$ schlechten Farben darstellt.

Beispiele

Eingabe 1

6 1
1 1 1
1 1 4
1 2 2
1 2 8
1 3 100

Ausgabe 1

108

Hinweis

Wähle den Pfad von Knoten $5$ zu Knoten $6$, der nacheinander die Knoten $5, 1, 6$ durchläuft und die Länge $8 + 100 = 108$ hat.

Dieser Pfad durchläuft keine Kante der Farbe $1$ und alle Kanten der Farbe $3$, daher sind die Farben $1, 3$ beide gut. Er durchläuft nur eine der beiden Kanten der Farbe $2$, daher ist Farbe $2$ schlecht.

Dieser Pfad hat genau eine schlechte Farbe und erfüllt somit die Bedingung. Es lässt sich beweisen, dass kein längerer gültiger Pfad existiert.

Eingabe 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

Ausgabe 2

35

Hinweis

Wähle den Pfad von Knoten $8$ zu Knoten $9$, der nacheinander die Knoten $8, 4, 2, 1, 3, 6, 9$ durchläuft und die Länge $8 + 5 + 3 + 4 + 6 + 9 = 35$ hat.

Dieser Pfad durchläuft alle Kanten der Farben $1, 2, 5$ und keine Kanten der Farben $3, 4$; somit gibt es keine schlechten Farben und die Bedingung ist erfüllt. Es lässt sich beweisen, dass kein längerer gültiger Pfad existiert.

Eingabe 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

Ausgabe 3

16

Hinweis

Wähle den Pfad von Knoten $7$ zu Knoten $8$, der nacheinander die Knoten $7, 2, 1, 3, 8$ durchläuft und die Länge $2 + 6 + 5 + 3 = 16$ hat.

Dieser Pfad durchläuft zwei der drei Kanten der Farbe $1$, daher ist Farbe $1$ schlecht. Er durchläuft alle Kanten der Farben $3, 4$ und keine Kanten anderer Farben, hat also genau eine schlechte Farbe und erfüllt die Bedingung.

Der Pfad von Knoten $7$ zu Knoten $9$ hat die Länge $17$, aber die Farben $1, 2$ sind beide schlecht, sodass er die Bedingung nicht erfüllt. Es lässt sich beweisen, dass kein gültiger Pfad mit einer Länge größer als $16$ existiert.

Beschränkungen

Für alle Testdaten gilt:

  • $2 \le n \le 2 \times 10^5$;
  • $k \in \{0, 1\}$;
  • Für jedes $i = 2, 3, \ldots, n$ gilt $1 \le p_i < i$, $1 \le c_i \le n$ und $0 \le w_i \le 10^9$.

Teilaufgaben

Diese Aufgabe verwendet gebündelte Tests mit sinnvollen Abhängigkeiten zwischen den Teilaufgaben.

Teilaufgabe $n \le$ $k =$ Besondere Eigenschaft Punkte
$1$ $200$ $0$ oder $1$ Keine $5$
$2$ $3000$ $0$ oder $1$ Keine $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$ Keine $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$ Keine $11$
$13$ $2 \times 10^5$ $1$ Keine $13$
  • Besondere Eigenschaft A: Für jede Farbe bilden alle Kanten dieser Farbe einen zusammenhängenden Teilgraphen.
  • Besondere Eigenschaft B: Jede Farbe kommt höchstens zweimal vor.
  • Besondere Eigenschaft C: Für jedes $i = 2, 3, \ldots, n$ wird $p_i$ unabhängig und gleichverteilt zufällig aus den ganzen Zahlen $1, 2, \ldots, i - 1$ gewählt.
  • Besondere Eigenschaft D: Für jede Farbe existiert ein einfacher Pfad mit Knoten $1$ als einem Endpunkt, der alle Kanten dieser Farbe enthält.

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.