……Чего ещё можно желать, кроме счастливого конца?
Дано дерево из $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$, содержащий все рёбра этого цвета.