题目描述
有一棵以节点 1 为根、节点编号为 1 到 n 的树。第 j 个果实位于节点 vj,恰好在第 dj 天成熟,只能在当天收获,收获后得到 wj 的果汁。
每天可以砍断任意条边,也可以一条边也不砍断。对于每条被砍断的边,获得以该边儿子为根的子树中当天成熟果实的果汁;这些子树会掉落,其中尚未成熟的果实全部丢失。请安排操作,使获得的果汁总量最大。
输入格式
从 magic.in 文件读入数据。
第一行包含 n,m,k,分别表示节点数、果实数和可能的最大成熟天数。接下来 n−1 行,第 i 行给出节点 i+1 的父亲 pi。接下来 m 行给出 vj,dj,wj。
输出格式
输出到 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≤100000,1≤m≤n−1,1≤k≤100000,1≤pi<i,2≤vj≤n 且两两不同,1≤dj≤k,1≤wj≤109。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 |
分值 |
测试点 |
附加条件 |
| 1 |
6 |
1∼2 |
n,k≤20 且所有 wj=1 |
| 2 |
3 |
3∼4 |
所有果实都在叶节点 |
| 3 |
11 |
5∼6 |
树是一条链且所有 wj=1 |
| 4 |
12 |
7∼9 |
k≤2 |
| 5 |
16 |
10∼12 |
k≤20 且所有 wj=1 |
| 6 |
13 |
13∼14 |
m≤1000 |
| 7 |
22 |
15∼17 |
所有 wj=1 |
| 8 |
17 |
18∼20 |
无额外限制 |