我们有一棵神奇的树:一棵在 $$$n$$$ 顶点上有根的树。顶点编号为 $$$1$$$ 到 $$$n$$$。顶点 $$$1$$$ 是根。
魔法树给了我们魔法果实。果实只生长在树的顶点,而不是根部。每个顶点最多包含一个水果。
现在是第 0 天,还没有水果成熟。每个水果只会在一天内成熟。对于每个水果,我们都会得到它生长的顶点 $$$v_j$$$、它成熟的日期 $$$d_j$$$ 以及如果我们在成熟时收获它,我们可以从中提取的魔法汁液 $$$w_j$$$ 量。
果实必须通过砍掉一些树枝来收获。每天,您可以砍下任意数量的树枝。你砍下的树的部分会掉到地上,你可以收集它们所包含的所有成熟的果实。所有未成熟时落到地上的水果都会被丢弃,并且不会从它们身上收集魔法汁液。
正式来说,每天您都可以擦除树的一些边缘。每当您这样做时,树都会分成多个连接的组件。然后,您删除所有不包含根的成分,并收获包含这些成分的所有成熟果实。
给出了对树的描述以及所有 $$$m$$$ 水果的位置、成熟日期和多汁性。计算我们可以从树上收获的魔法汁液的最大总量。
输入
第一行包含三个空格分隔的整数 $$$n$$$ ($$$2 \le n \le 100,000$$$)、$$$m$$$ ($$$1 \le m \le n-1$$$) 和 $$$k$$$ ($$$1 \le k \le 100,000$$$) – 顶点数,水果的数量,以及水果成熟的最长天数。
以下 $$$n-1$$$ 行包含整数 $$$p_2, \dots, p_n$$$,每行一个。对于每个 $$$i$$$(从 $$$2$$$ 到 $$$n$$$,包括在内),顶点 $$$p_i$$$ ($$$1 \leq p_i \le i-1$$$) 是顶点 $$$i$$$ 的父节点。
最后 $$$m$$$ 行描述一种水果。这些行中的第 $$$j$$$ 的形式为“$$$v_j\ d_j\ w_j$$$”($$$2 \le v_j \le n$$$、$$$1 \le d_j \le k$$$、$$$1 \le w_j \le 10^9$$$)。
保证没有顶点包含多个水果(即,值 $$$v_j$$$ 是不同的)。
输出
输出一行包含一个整数,即我们可以从树上收获的最大魔法果汁量。
示例
输入 #1
6 4 10 1 2 1 4 4 3 4 5 4 7 2 5 4 1 6 9 3
输出 #1
9
注意
评分:
子任务 1(6 分):对于所有 $$$j$$$,$$$n、k \leq 20$$$ 和 $$$w_j = 1$$$
子任务2(3分):果实只生长在树的叶子上
子任务 3(11 分):对于每个 $$$i$$$,$$$p_i = i-1$$$,对于所有 $$$j$$$,$$$w_j = 1$$$
子任务 4(12 分):$$$k \leq 2$$$
子任务 5(16 分):$$$k \leq 20$$$,并且 $$$w_j = 1$$$ 对于所有 $$$j$$$
子任务 6(13 分):$$$m \leq 1,000$$$
子任务 7(22 分):$$$w_j = 1$$$ 对于所有 $$$j$$$
子任务8(17分):无额外限制
在示例输入中,一个最佳解决方案如下所示:
- 在第 4 天,切割顶点 4 和 5 之间的边缘,并用 1 单位魔法果汁收获成熟的果实。同一天,切割顶点 1 和 2 之间的边,从顶点 3 的成熟果实中收获 5 单位魔法汁液。
- 第 7 天,什么也不做。 (我们可以收获顶点 4 中刚刚成熟的果实,但这样做并不是最佳选择。)
- 在第9天,切割顶点1和4之间的边缘。丢弃顶点4中不再成熟的水果,并从顶点6成熟的水果中收获3单位魔法果汁。(或者,我们可以通过切割顶点4和6之间的边缘来达到相同的效果。)