B. Волшебное дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

У нас есть волшебное дерево: корневое дерево с $$$n$$$ вершинами. Вершины пронумерованы от $$$1$$$ до $$$n$$$. Вершина $$$1$$$ является корнем.

Волшебное дерево дает волшебные плоды. Плоды растут только в тех вершинах, которые не являются корнем. В каждой вершине может быть максимум один плод.

Сейчас день 0 и ни один плод еще не поспел. Каждый плод будет спелым лишь в течение одного дня. Для каждого плода известна вершина $$$v_j$$$, где он растет, день $$$d_j$$$, когда он будет спелым, а также объем $$$w_j$$$ волшебного сока, который мы можем получить, если соберем этот плод в тот день, когда он спелый.

Плоды нужно собирать, отрезая некоторые ветви дерева. Каждый день можно отрезать сколько угодно ветвей. Те части дерева, которые вы отрежете, упадут на землю, и вы сможете собрать все спелые плоды, которые там есть. Все неспелые плоды, упавшие на землю, использовать для получения сока нельзя.

Формально каждый день вы можете удалить некоторые ребра дерева. Когда вы делаете это, дерево распадается на несколько связных компонент. Вы удаляете все компоненты, не содержащие корень, и собираете все спелые плоды в этих компонентах.

Вам дано описание дерево вместе с положением, временем поспевания и сочностью каждого из $$$m$$$ плоды. Найдите максимальный объем сока, который вы можете получить.

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

Первая строка содержит три целых числа $$$n$$$ ($$$2 \le n \le 100,000$$$), $$$m$$$ ($$$1 \le m \le n-1$$$) и $$$k$$$ ($$$1 \le k \le 100,000$$$) — количество вершин, количество плодов и максимальное количество дней, через которое плоды могут стать спелыми.

Следующие $$$n-1$$$ строк содержат числа $$$p_2, \dots, p_n$$$ по одному в строке. Для всех $$$i$$$ (от $$$2$$$ до $$$n$$$ включительно) вершина $$$p_i$$$ ($$$1 \leq p_i \le i-1$$$) является предком вершины $$$i$$$.

Каждая из последних $$$m$$$ строк описывает один плод. $$$j$$$-я из этих строк имеет вид «$$$v_j\ d_j\ w_j$$$» ($$$2 \le v_j \le n$$$, $$$1 \le d_j \le k$$$, $$$1 \le w_j \le 10^9$$$).

Гарантируется, что никакая вершина не содержит более, чем один плод (т. е. все значения $$$v_j$$$ различны).

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

Выведите одно целое число — максимальных объем волшебного сока, который вы можете получить с дерева.

Система оценки

Подзадача 1 (6 баллов): $$$n, k \leq 20$$$, а также $$$w_j = 1$$$ для всех $$$j$$$

Подзадача 2 (3 балла): фрукты растут только в листьях дерева

Подзадача 3 (11 баллов): $$$p_i = i-1$$$ для всех $$$i$$$, а также $$$w_j = 1$$$ для всех $$$j$$$

Подзадача 4 (12 баллов): $$$k \leq 2$$$

Подзадача 5 (16 баллов): $$$k \leq 20$$$, а также $$$w_j = 1$$$ для всех $$$j$$$

Подзадача 6 (13 баллов): $$$m \leq 1,000$$$

Подзадача 7 (22 балла): $$$w_j = 1$$$ для всех $$$j$$$

Подзадача 8 (17 баллов): нет дополнительных ограничений

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

В примере одно из оптимальных решений выглядит так:

  • В день 4 отрезать ребро между вершинами 4 и 5 и собрать спелый плод с 1 единицей волшебного сока. В тот же день отрезать ребро между вершинами 1 и 2 и собрать 5 единиц волшебного сока со спелого плода в вершине 3.
  • В день 7 ничего не делать. Мы могли бы собрать плод из вершины 4, но это не оптимально.
  • В день 9 отрезать ребро между вершинами 1 и 4. Плод в вершине 4 уже не спелый, так что его нужно выбросить, а собрать 3 единицы волшебного сока со спелого фрукта в вершине 6. Кроме того, того же эффекта мы бы добились, отрезав ребро между вершинами 4 и 6.