题目描述

译自 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

数据范围与提示

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