题目描述

有一棵以 $1$ 为根，节点从 $1$ 到 $n$ 编号的树。

在这棵树上有许多果实，第 $j$ 个果实会于第 $d_j$ 天在节点 $v_j$ 成熟，并且在收获后可获得 $w_j$ 的果汁。

第 $j$ 个果实仅能在第 $d_j$ 天收获。

收获的方式是断掉这棵树的一条边，这会获得在这条边上作为儿子的那个点的子树上的当天成熟的果实的果汁。

您要求出最多可以获得多少果汁。

输入格式

第一行为三个整数 $n,m,k$，分别表示节点的个数，果实的个数和果实可能成熟天数的最大值。

接下来 $n-1$ 行，一行一个整数 $p_i$，表示 $i+1$ 号节点的父亲是 $p_i$。

接下来 $m$ 行一行三个整数 $v_j,d_j,w_j$。

输出格式

一行一个数，表示最多可以获得多少果汁。

6 4 10
1
2
1
4
4
3 4 5
4 7 2
5 4 1
6 9 3

9

提示

样例解释

最优方案如下：

• 在第四天，断掉 $(4,5)$ 和 $(1,2)$，获得第一个和第三个果实，获得的果汁数量累计为 $6$。
• 在第七天，虽然我们有一个果实成熟，但是我们最好什么都不干。
• 在第九天，断掉 $(1,4)$，获得最后一个果实，获得的果汁数量累计为 $9$。

数据范围

对于 $100\%$ 的数据，保证 $2\le n\le 10^5$，$1\le m\le n-1$，$1\le k\le 10^5$，$1\le p_i\le i-1$，$2\le v_j\le n$，$1\le d_j\le k$，$1\le w_j\le 10^9$，$v_j$ 互不相同。

详细子任务限制及分值如下表：

说明

本题译自 Central-European Olympiad in Informatics 2019 Day 2 T2 Magic Tree。