QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100 Hackable ✓

#21438. Another Story END

Statistics

……Чого ще можна бажати, окрім щасливого фіналу?

Задано дерево з $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$, який містить усі ребра цього кольору.

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.