该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile3166.zip](file://AdditionalFile3166.zip?type=additional_file)

#3166. 「CEOI2019」魔法树

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 CEOI 2019 Day2 T2「Magic Tree」

现在有一颗魔法树，总共有 $n$ 个节点，编号从 $1$ 至 $n$。$1$ 节点是它的根。除 $1$ 节点外的每个节点最多长有一个魔法果实。一个长在 $v_j$ 节点的魔法果实恰会在第 $d_j$ 天成熟，在成熟时将其收获可以获得 $w_j$ 单位的果汁。

每天你可以砍下树上的某些边，然后当天与 $1$ 节点不再联通的果实如果恰好在当天成熟，则能够收获该果实的果汁。

请找出最优方案下，总共能够收获的果汁量。

输入格式

第一行三个正整数 $n, m, k$，分别表示节点数，果实数，所有果实成熟时间的上限。

接下来共 $n-1$ 行，每行一个正整数分别为 $p_2, p_3, \dots, p_n$，$p_i$ 表示 $i$ 节点的父亲。

接下来共 $m$ 行，每行三个正整数 $v_j, d_j, w_j$，分别表示该果实生长的节点编号，成熟日期，能收获的果汁。保证 $v_j$ 互不相同。

输出格式

输出一行一个整数，表示最优方案下，总共能够收获的果汁量。

样例

输入

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

输出

9

• 在第 $4$ 天，砍下 $5$ 号节点连接父亲的边，从 $5$ 号节点上的果实收获 $1$ 单位的果汁。砍下 $2$ 节点连接父亲的边，从 $3$ 号节点上的果实收获 $5$ 单位的果汁。
• 在第 $9$ 天，砍下 $4$ 号节点连接父亲的边，从 $6$ 号节点上的果实收获 $3$ 单位的果汁。

数据范围与提示

对于 $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$。