CF1193B.Magic Tree

We have a magic tree: a rooted tree on $n$ vertices. The vertices are numbered $1$ through $n$. Vertex $1$ is the root.

The magic tree gives us magic fruit. The fruit only grows in vertices of the tree other than the root. Each vertex contains at most one piece of fruit.

It is now day 0 and no fruit is ripe yet. Each fruit will only be ripe for a single day. For each fruit, we are given the vertex $v_j$ where it grows, the day $d_j$ on which it will be ripe, and the amount $w_j$ of magic juice we can extract from it if we harvest it when it is ripe.

The fruits have to be harvested by cutting some branches of the tree. On each day, you may cut as many branches of the tree as you like. The parts of the tree you cut off will fall to the ground and you can collect all the ripe fruits they contain. All fruits that fall to the ground when they are not ripe are discarded and no magic juice is collected from them.

Formally, on each day, you may erase some edges of the tree. Whenever you do so, the tree will split into multiple connected components. You then erase all components that do not contain the root and you harvest all ripe fruits those components contained.

Given is a description of the tree together with the locations, ripening days and juiciness of all $m$ fruits. Calculate the maximum total amount of magic juice we can harvest from the tree.

我们有一棵“魔法树”：一棵包含 $n$ 个顶点的有根树。顶点编号为 $1$ 到 $n$，其中顶点 $1$ 是树根。

这棵魔法树会结出魔法果实。果实只生长在除根以外的顶点上，且每个顶点至多结一颗果实。

当前是第 $0$ 天，所有果实均未成熟。每颗果实仅在某一天成熟（即仅在该天可被采摘）。对于第 $j$ 颗果实，已知其生长位置（顶点）$v_j$、成熟日期（天数）$d_j$，以及若在其成熟当天采摘所能获得的魔法果汁量 $w_j$。

采摘果实需通过砍断树的某些边来实现。每天你可以砍断任意数量的边。被砍断后脱落至地面的部分所含的所有成熟果实均可被收集；但若果实随枝条一起掉落时尚未成熟，则该果实被丢弃，无法获得任何果汁。

形式化地讲：每天你可以删除树中的若干条边。执行此操作后，树将分裂成多个连通分量。随后你删去所有不包含根节点的连通分量，并收获这些被删去分量中所有已成熟的果实。

现给出该树的结构描述，以及全部 $m$ 颗果实的生长位置、成熟日期和果汁量。请计算我们能从该树中收获的魔法果汁总量的最大值。

The first line contains three space-separated integers $n$ ($2 \le n \le 100,000$), $m$ ($1 \le m \le n-1$) and $k$ ($1 \le k \le 100,000$) – the number of vertices, the number of fruits, and the maximum day on which a fruit may become ripe.

The following $n-1$ lines contain the integers $p_2, \dots, p_n$, one per line. For each $i$ (from $2$ to $n$, inclusive), vertex $p_i$ ($1 \leq p_i \le i-1$) is the parent of vertex $i$.

Each of the last $m$ lines describes one fruit. The $j$-th of these lines has the form "$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$).

It is guaranteed that no vertex contains more than one fruit (i.e., the values $v_j$ are distinct).

第一行包含三个以空格分隔的整数 $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$ 的值互不相同）。

Output a single line with a single integer, the maximum amount of magic juice we can harvest from the tree.

输出一行，包含一个整数，表示我们能从树上收获的最大魔法果汁量。

In the example input, one optimal solution looks as follows:

• On day 4, cut the edge between vertices 4 and 5 and harvest a ripe fruit with 1 unit of magic juice. On the same day, cut the edge between vertices 1 and 2 and harvest 5 units of magic juice from the ripe fruit in vertex 3.
• On day 7, do nothing. (We could harvest the fruit in vertex 4 that just became ripe, but doing so is not optimal.)
• On day 9, cut the edge between vertices 1 and 4. Discard the fruit in vertex 4 that is no longer ripe, and harvest 3 units of magic juice from the ripe fruit in vertex 6. (Alternately, we could achieve the same effect by cutting the edge between vertices 4 and 6.)

在样例输入中，一个最优解如下所示：

• 第 4 天：切断顶点 4 与顶点 5 之间的边，并采摘一颗已成熟的果实，获得 1 单位魔力果汁；同一天，切断顶点 1 与顶点 2 之间的边，并从顶点 3 处已成熟的果实中收获 5 单位魔力果汁。
• 第 7 天：不进行任何操作。（此时顶点 4 的果实恰好成熟，我们本可采摘它，但这样做并非最优。）
• 第 9 天：切断顶点 1 与顶点 4 之间的边；丢弃顶点 4 处已不再成熟的果实，并从顶点 6 处已成熟的果实中收获 3 单位魔力果汁。（或者，我们也可通过切断顶点 4 与顶点 6 之间的边来达到相同效果。）