#CW55. 果树魔法(magic)

果树魔法(magic)

题目描述

有一棵以节点 11 为根、节点编号为 11 到 nn 的树。第 jj 个果实位于节点 vjv_j,恰好在第 djd_j 天成熟,只能在当天收获,收获后得到 wjw_j 的果汁。

每天可以砍断任意条边,也可以一条边也不砍断。对于每条被砍断的边,获得以该边儿子为根的子树中当天成熟果实的果汁;这些子树会掉落,其中尚未成熟的果实全部丢失。请安排操作,使获得的果汁总量最大。

输入格式

从 magic.in 文件读入数据。

第一行包含 n,m,kn,m,k,分别表示节点数、果实数和可能的最大成熟天数。接下来 n−1n-1 行,第 ii 行给出节点 i+1i+1 的父亲 pip_i。接下来 mm 行给出 vj,dj,wjv_j,d_j,w_j。

输出格式

输出到 magic.out 文件。

输出一个整数,表示可以获得的最大果汁总量。

样例 1 输入

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

样例 1 输出

9

数据范围

满足 2≤n≤1000002 \le n \le 100000,1≤m≤n−11 \le m \le n-1,1≤k≤1000001 \le k \le 100000,1≤pi<i1 \le p_i < i,2≤vj≤n2 \le v_j \le n 且两两不同,1≤dj≤k1 \le d_j \le k,1≤wj≤1091 \le w_j \le 10^9。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 6 1∼21\sim 2 n,k≤20n,k \le 20 且所有 wj=1w_j = 1
2 3 3∼43\sim 4 所有果实都在叶节点
3 11 5∼65\sim 6 树是一条链且所有 wj=1w_j = 1
4 12 7∼97\sim 9 k≤2k \le 2
5 16 10∼1210\sim 12 k≤20k \le 20 且所有 wj=1w_j = 1
6 13 13∼1413\sim 14 m≤1000m \le 1000
7 22 15∼1715\sim 17 所有 wj=1w_j = 1
8 17 18∼2018\sim 20 无额外限制