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