魔法树 - 题目

我们有一棵魔法树：一棵有 $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_i$。对于每个 $i$（从 $2$ 到 $n$），顶点 $p_i$ ($1 \le 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$ 的值各不相同）。

输出一行，包含一个整数，表示可以从树中收获的魔法果汁的最大总量。

在样例输入中，一种最优解如下：

在第 4 天，砍掉顶点 4 和 5 之间的边，收获一个含有 1 单位魔法果汁的成熟果实。在同一天，砍掉顶点 1 和 2 之间的边，从顶点 3 的成熟果实中收获 5 单位魔法果汁。
在第 7 天，什么都不做。（我们可以收获顶点 4 中刚刚成熟的果实，但这样做不是最优的。）
在第 9 天，砍掉顶点 1 和 4 之间的边。丢弃顶点 4 中不再成熟的果实，并从顶点 6 的成熟果实中收获 3 单位魔法果汁。（或者，我们可以通过砍掉顶点 4 和 6 之间的边达到同样的效果。）

QOJ.ac