CF1193B Magic Tree

我们有一棵魔法树：一棵有 $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 \le i \le 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$ 两两不同）。

输出一行一个整数，表示你最多能收获的魔法汁液总量。

在样例输入中，一种最优方案如下： - 第 4 天，砍断顶点 4 和 5 之间的边，收获成熟的果实，获得 1 单位魔法汁液。同一天，砍断顶点 1 和 2 之间的边，收获顶点 3 上成熟的果实，获得 5 单位魔法汁液。 - 第 7 天，不做任何操作。（此时可以收获刚成熟的顶点 4 上的果实，但这样做不是最优的。） - 第 9 天，砍断顶点 1 和 4 之间的边，丢弃已经不再成熟的顶点 4 上的果实，收获顶点 6 上成熟的果实，获得 3 单位魔法汁液。（或者，也可以砍断顶点 4 和 6 之间的边，效果相同。） 由 ChatGPT 4.1 翻译