Олимпиадный тренинг

Задача . D. Кактусомания

Задача

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

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

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

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

Входные данные

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

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

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

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

Выходные данные

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

Примеры

№	Входные данные	Выходные данные
1	7 3 1 1 2 2 3 3 4 5 1 6 7 1 2 3 1	2

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет