#3166. 「CEOI2019」魔法树

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

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

Subtask # 分值 特殊限制
1 6 n, k\le 20, w_j = 1
2 3 果实都生长在叶子上
3 11 p_i = i-1, w_j = 1
4 12 k\le 2
5 16 k\le 20, w_j = 1
6 13 m\le 10^3
7 22 w_j = 1
8 17