QOJ.ac

QOJ

Limite de temps : 2 s Limite de mémoire : 512 MB Points totaux : 100 Hackable ✓

#21438. Another Story END

Statistiques

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

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.