题目描述
译自 CEOI 2019 Day2 T2「Magic Tree」
现在有一颗魔法树,总共有 n 个节点,编号从 1 至 n。1 节点是它的根。除 1 节点外的每个节点最多长有一个魔法果实。一个长在 vj 节点的魔法果实恰会在第 dj 天成熟,在成熟时将其收获可以获得 wj 单位的果汁。
每天你可以砍下树上的某些边,然后当天与 1 节点不再联通的果实如果恰好在当天成熟,则能够收获该果实的果汁。
请找出最优方案下,总共能够收获的果汁量。
输入格式
第一行三个正整数 n,m,k,分别表示节点数,果实数,所有果实成熟时间的上限。
接下来共 n−1 行,每行一个正整数分别为 p2,p3,…,pn,pi 表示 i 节点的父亲。
接下来共 m 行,每行三个正整数 vj,dj,wj,分别表示该果实生长的节点编号,成熟日期,能收获的果汁。保证 vj 互不相同。
输出格式
输出一行一个整数,表示最优方案下,总共能够收获的果汁量。
样例
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≤n≤105,1≤m≤n−1,1≤k≤105,1≤pi≤i−1,2≤vj≤n,1≤dj≤k,1≤wj≤109。
Subtask # |
分值 |
特殊限制 |
1 |
6 |
n,k≤20,wj=1 |
2 |
3 |
果实都生长在叶子上 |
3 |
11 |
pi=i−1,wj=1 |
4 |
12 |
k≤2 |
5 |
16 |
k≤20,wj=1 |
6 |
13 |
m≤103 |
7 |
22 |
wj=1 |
8 |
17 |
|