Финальный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"D" Кактусомания
Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

Маша очень любит кактусы. В детстве Маша посадила дерево, и сейчас оно стало достаточно большим. Маша хочет из своего дерева сделать самый красивый кактус.

Напомним, что дерево — это неориентированный связный граф, в котором нет циклов. А кактус — это неориентированный связный граф, через каждую вершину которого проходит не более одного простого цикла.

У Маши есть дополнительные ребра, которые она может добавить к дереву. Для каждого ребра Маша знает, какие вершины оно должно соединять, и красоту этого ребра. Маша может добавить некоторые из этих ребер к дереву, если после их добавления получившийся граф будет кактусом. Красота полученного графа равна сумме всех значений красоты добавленных ребер.

Помогите Маше выяснить, какую максимальную красоту итогового кактуса Маша может получить.

Формат входных данных

В первой строке записаны два целых числа n и m — число вершин в дереве и число имеющихся у Маши дополнительных ребер, соответственно (3 ≤ n ≤ 2·105; 0 ≤ m ≤ 2·105).

Пусть Машино дерево имеет корень в вершине 1. В следующей строке записано n - 1 целых чисел: p2, p3, ..., pn, где pi — номер родителя вершины i в дереве — первая вершина на пути от вершины i до корня (1 ≤ pi < i).

В следующих m строках задано по три целых числа ui, vi и ci — вершины, которые могут быть соединены дополнительным ребром, которые Маша может добавить к дереву, и красоту этого ребра (1 ≤ ui, vi ≤ n; ui ≠ vi; 1 ≤ ci ≤ 104).

Гарантируется, что ни одно из дополнительных ребер не совпадает с ребром дерева.

Формат выходных данных

Выведите одно целое число — максимально возможную суммарную красоту кактуса, которую Маша может получить.

Примеры
Входные данные
7 3
1 1 2 2 3 3
4 5 1
6 7 1
2 3 1
Выходные данные
2
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.