… Czego więcej można chcieć oprócz szczęśliwego zakończenia?
Dane jest drzewo o $n$ wierzchołkach ponumerowanych od $1$ do $n$, ukorzenione w wierzchołku $1$. Dla każdego $i = 2, 3, \ldots, n$, pomiędzy wierzchołkiem $i$ a jego ojcem $p_i$ istnieje dwukierunkowa krawędź o kolorze $c_i$ i długości $w_i$.
Dla koloru $c$ występującego w drzewie, jeśli ścieżka prosta przechodzi przez wszystkie krawędzie koloru $c$ albo nie przechodzi przez żadną krawędź koloru $c$, to mówimy, że kolor $c$ jest dobry dla tej ścieżki; w przeciwnym razie mówimy, że kolor $c$ jest zły dla tej ścieżki.
Dana jest liczba całkowita $k \in \{0, 1\}$. Wyznacz maksymalną długość ścieżki prostej mającej co najwyżej $k$ złych kolorów. Długość ścieżki definiujemy jako sumę długości wszystkich krawędzi na tej ścieżce.
Możesz wybrać ten sam wierzchołek jako oba końce ścieżki; w takim przypadku ścieżka nie przechodzi przez żadną krawędź i ma długość $0$.
Zauważ, że krawędzie tego samego koloru nie muszą tworzyć spójnego podgrafu, a długość krawędzi może wynosić $0$.
Wejście
Pierwszy wiersz zawiera dwie liczby całkowite $n, k$, oznaczające odpowiednio liczbę wierzchołków oraz maksymalną dopuszczalną liczbę złych kolorów.
$i$-ty z kolejnych $n - 1$ wierszy zawiera trzy liczby całkowite $p_i, c_i, w_i$, oznaczające, że między wierzchołkiem $i$ a wierzchołkiem $p_i$ istnieje dwukierunkowa krawędź o kolorze $c_i$ i długości $w_i$.
Wyjście
Wypisz jeden wiersz zawierający jedną liczbę całkowitą, oznaczającą maksymalną długość ścieżki prostej mającej co najwyżej $k$ złych kolorów.
Przykład
Wejście 1
6 1 1 1 1 1 1 4 1 2 2 1 2 8 1 3 100
Wyjście 1
108
Uwagi
Wybierzmy ścieżkę z wierzchołka $5$ do wierzchołka $6$, przechodzącą kolejno przez wierzchołki $5, 1, 6$, o długości $8 + 100 = 108$.
Ta ścieżka nie przechodzi przez żadną krawędź koloru $1$ i przechodzi przez wszystkie krawędzie koloru $3$, zatem kolory $1, 3$ są dobre. Przechodzi tylko przez jedną z dwóch krawędzi koloru $2$, więc kolor $2$ jest zły.
Ta ścieżka ma dokładnie jeden zły kolor, co spełnia warunki zadania. Można udowodnić, że nie istnieje dłuższa poprawna ścieżka.
Wejście 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
Wyjście 2
35
Uwagi
Wybierzmy ścieżkę z wierzchołka $8$ do wierzchołka $9$, przechodzącą kolejno przez wierzchołki $8, 4, 2, 1, 3, 6, 9$, o długości $8 + 5 + 3 + 4 + 6 + 9 = 35$.
Ta ścieżka przechodzi przez wszystkie krawędzie kolorów $1, 2, 5$ i nie przechodzi przez żadną krawędź kolorów $3, 4$, zatem nie ma złych kolorów i spełnia warunki zadania. Można udowodnić, że nie istnieje dłuższa poprawna ścieżka.
Wejście 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
Wyjście 3
16
Uwagi
Wybierzmy ścieżkę z wierzchołka $7$ do wierzchołka $8$, przechodzącą kolejno przez wierzchołki $7, 2, 1, 3, 8$, o długości $2 + 6 + 5 + 3 = 16$.
Ta ścieżka przechodzi przez dwie z trzech krawędzi koloru $1$, więc kolor $1$ jest zły. Przechodzi przez wszystkie krawędzie kolorów $3, 4$ i nie przechodzi przez żadną krawędź innych kolorów, więc ma dokładnie jeden zły kolor i spełnia warunki zadania.
Ścieżka z wierzchołka $7$ do wierzchołka $9$ ma długość $17$, ale kolory $1, 2$ są oba złe, więc nie spełnia warunków zadania. Można udowodnić, że nie istnieje poprawna ścieżka o długości większej niż $16$.
Ograniczenia
Dla wszystkich danych testowych spełnione są warunki:
- $2 \le n \le 2 \times 10^5$;
- $k \in \{0, 1\}$;
- Dla każdego $i = 2, 3, \ldots, n$ zachodzi $1 \le p_i < i$, $1 \le c_i \le n$ oraz $0 \le w_i \le 10^9$.
Podzadania
W tym zadaniu stosowane jest testowanie pakietowe (bundled testing) z rozsądnymi zależnościami między podzadaniami.
| Podzadanie | $n \le$ | $k =$ | Własność specjalna | Punkty |
|---|---|---|---|---|
| $1$ | $200$ | $0$ lub $1$ | Brak | $5$ |
| $2$ | $3000$ | $0$ lub $1$ | Brak | $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$ | Brak | $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$ | Brak | $11$ |
| $13$ | $2 \times 10^5$ | $1$ | Brak | $13$ |
- Własność specjalna A: Dla każdego koloru wszystkie krawędzie tego koloru tworzą spójny podgraf.
- Własność specjalna B: Każdy kolor występuje co najwyżej dwa razy.
- Własność specjalna C: Dla każdego $i = 2, 3, \ldots, n$, liczba $p_i$ jest losowana niezależnie z jednostajnym prawdopodobieństwem spośród liczb całkowitych $1, 2, \ldots, i - 1$.
- Własność specjalna D: Dla każdego koloru istnieje ścieżka prosta mająca wierzchołek $1$ jako jeden z końców, która zawiera wszystkie krawędzie tego koloru.