QOJ.ac

QOJ

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

#21438. Another Story END

Statistiques

……Чего ещё можно желать, кроме счастливого конца?

Дано дерево из $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.