← 返回比赛

已结束 GESP巅峰赛#24

← 上一题下一题 →

A5125 | $打工$

时间限制4s

内存限制1024MB

通过 / 提交0/0

题目描述

$Alice$ 学校附近的地图可以看作一棵有 $n$ 个结点的树，通过树的每条边需要消耗 $1$ 单位时间。$Alice$ 的学校位于树的根结点处，编号为 $1$。树的一些结点是打工地点，共有 $m$ 个。在每个打工地点，$Alice$ 可以打工 $w$ 单位时间，获得 $v$ 的报酬，每个打工地点只能打工一次。请帮助 $Alice$ 算一算，如果她从学校出发，最终回到学校，在 $W$ 单位时间内最多能赚多少钱。

输入格式

第一行包含三个正整数 $n$, $m$ 和 $W$ ，其含义见题目描述。 用例的第二行包含 $n-1$ 个正整数 $a_2, a_3, \ldots, a_n$ ，其中 $a_i$ 表示节点 $i$ 的父节点是 $a_i$。 用例的接下来 $m$ 行，每行包含三个正整数 $u_j$, $w_j$ 和 $v_j$ ，表示第 $j$ 个打工地点在结点 $u_j$，耗时 $w_j$，报酬 $v_j$。数据保证，所有打工地点的结点编号互不相同。

输出格式

对于每个测试用例，输出的唯一一行包含一个整数，表示 Alice 最多能赚多少钱。

输入输出样例

输入 #1

7 3 10
1 1 2 2 3 3
4 1 1
6 1 2
7 1 3

输出 #1

输入 #2

7 3 7
1 1 2 2 3 3
4 1 1
6 1 2
7 1 3

输出 #2

C++ 编辑器

输入

输出