……Чого ще можна бажати, окрім щасливого фіналу?
Задано дерево з $n$ вершин, пронумерованих від $1$ до $n$, з коренем у вершині $1$. Для кожного $i = 2, 3, \ldots, n$ між вершиною $i$ та її батьком $p_i$ є двонаправлене ребро кольору $c_i$ та довжини $w_i$.
Для кольору $c$, що зустрічається в дереві, якщо простий шлях проходить через усі ребра кольору $c$ або не проходить через жодне ребро кольору $c$, то колір $c$ називається хорошим для цього шляху; інакше колір $c$ називається поганим для цього шляху.
Задано ціле число $k \in \{0, 1\}$. Знайдіть максимальну довжину простого шляху, у якого кількість поганих кольорів не перевищує $k$. Довжина шляху визначається як сума довжин усіх ребер на цьому шляху.
Ви можете вибрати одну й ту саму вершину як обидва кінці шляху; у цьому випадку шлях не проходить через жодне ребро і має довжину $0$.
Зверніть увагу, що ребра одного кольору не обов'язково утворюють зв'язний підграф, а довжина ребра може дорівнювати $0$.
Вхідні дані
Перший рядок містить два цілі числа $n, k$, які позначають кількість вершин і максимально допустиму кількість поганих кольорів відповідно.
$i$-й із наступних $n - 1$ рядків містить три цілі числа $p_i, c_i, w_i$, які означають, що між вершиною $i$ та вершиною $p_i$ є двонаправлене ребро кольору $c_i$ та довжини $w_i$.
Вихідні дані
Виведіть один рядок, що містить одне ціле число — максимальну довжину простого шляху з не більш ніж $k$ поганими кольорами.
Приклади
Вхідні дані 1
6 1 1 1 1 1 1 4 1 2 2 1 2 8 1 3 100
Вихідні дані 1
108
Примітка
Виберемо шлях від вершини $5$ до вершини $6$, який послідовно проходить через вершини $5, 1, 6$, його довжина становить $8 + 100 = 108$.
Цей шлях не проходить через жодне ребро кольору $1$ і проходить через усі ребра кольору $3$, тому кольори $1, 3$ є хорошими. Він проходить лише через одне з двох ребер кольору $2$, тому колір $2$ є поганим.
Цей шлях має рівно один поганий колір, що задовольняє умову. Можна довести, що довшого допустимого шляху не існує.
Вхідні дані 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
Вихідні дані 2
35
Примітка
Виберемо шлях від вершини $8$ до вершини $9$, який послідовно проходить через вершини $8, 4, 2, 1, 3, 6, 9$, його довжина становить $8 + 5 + 3 + 4 + 6 + 9 = 35$.
Цей шлях проходить через усі ребра кольорів $1, 2, 5$ і не проходить через жодне ребро кольорів $3, 4$, тому не має поганих кольорів і задовольняє умову. Можна довести, що довшого допустимого шляху не існує.
Вхідні дані 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
Вихідні дані 3
16
Примітка
Виберемо шлях від вершини $7$ до вершини $8$, який послідовно проходить через вершини $7, 2, 1, 3, 8$, його довжина становить $2 + 6 + 5 + 3 = 16$.
Цей шлях проходить через два з трьох ребер кольору $1$, тому колір $1$ є поганим. Він проходить через усі ребра кольорів $3, 4$ і не проходить через жодне ребро інших кольорів, тому має рівно один поганий колір і задовольняє умову.
Шлях від вершини $7$ до вершини $9$ має довжину $17$, але обидва кольори $1, 2$ є поганими, що не задовольняє умову. Можна довести, що допустимого шляху довжиною понад $16$ не існує.
Обмеження
Для всіх тестових даних виконується:
- $2 \le n \le 2 \times 10^5$;
- $k \in \{0, 1\}$;
- Для кожного $i = 2, 3, \ldots, n$ виконується $1 \le p_i < i$, $1 \le c_i \le n$, $0 \le w_i \le 10^9$.
Підзадачі
У цій задачі використовується пакетне тестування з розумними залежностями між підзадачами.
| Підзадача | $n \le$ | $k =$ | Особлива властивість | Бали |
|---|---|---|---|---|
| $1$ | $200$ | $0$ або $1$ | Немає | $5$ |
| $2$ | $3000$ | $0$ або $1$ | Немає | $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$ | Немає | $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$ | Немає | $11$ |
| $13$ | $2 \times 10^5$ | $1$ | Немає | $13$ |
- Особлива властивість A: Для кожного кольору всі ребра цього кольору утворюють зв'язний підграф.
- Особлива властивість B: Кожен колір зустрічається щонайбільше двічі.
- Особлива властивість C: Для кожного $i = 2, 3, \ldots, n$ значення $p_i$ вибирається незалежно та рівноймовірно з цілих чисел $1, 2, \ldots, i - 1$.
- Особлива властивість D: Для кожного кольору існує простий шлях з одним із кінців у вершині $1$, який містить усі ребра цього кольору.