Magic Tree

题意翻译

有一颗n个顶点上的有根树。顶点编号为1到n。 顶点1是根。 这个树结只生长在树的顶点而不是根的果实。每个顶点最多包含一个果实。 现在是第0天，还没有水果成熟。每种水果只会在一天内成熟。对于每个果实，我们给出生长的顶点$v_j$成熟的日期$d_j$以及在成熟时收获它，我们可以提取魔法汁的量$w_j$。 必须通过切割树的一些分枝来收获果实。 在每一天，您可以根据需要切割树的多个分支。你切掉的树的部分会掉到地上，你可以收获它们所含的成熟的果实的魔法汁。 所有未成熟时倒在地上的水果将无法收获魔法汁（被丢弃） 每天都可以擦除树的某些边缘。 每当您这样做时，树将分裂成多个连接的部分。 然后删除所有不含根的部分，并收获所有包含成熟果实的部分。 给出树的描述以及所有m个果实的位置，成熟日和魔法汁量。 计算我们可以从树上收获的魔法汁的最大量。 #### 输入 第一行包含三个空格分隔的整数：顶点数n（$2≤n≤100,000$），果实数m（$1≤m≤n-1$）和果实成熟最长日期k（$1≤k≤100,000$） 以下n-1行包含整数$p_2$,$...$,$p_n$，每行一个。 对于每个i（从2到n(包含2和n)），顶点$p_i$（$1≤p_i≤i-1$）是顶点i的父节点。 最后m行中的每一行描述一种果实。 这些行中的第j个是“$v_j$ $d_j$ $w_j$”的形式（$2≤v_j≤n$，$1≤d_j≤k$，$1≤w_j≤10^9$）。 保证没有顶点包含多个果实（即$v_j$的值是不同的）。 #### 输出 一个整数，代表可以提取出魔法汁的最大量。

题目描述

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.

输入输出格式

输入格式

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).

输出格式

Output a single line with a single integer, the maximum amount of magic juice we can harvest from the tree. Scoring Subtask 1 (6 points): $ n, k \leq 20 $ , and $ w_j = 1 $ for all $ j $ Subtask 2 (3 points): fruits only grow in the leaves of the tree Subtask 3 (11 points): $ p_i = i-1 $ for each $ i $ , and $ w_j = 1 $ for all $ j $ Subtask 4 (12 points): $ k \leq 2 $ Subtask 5 (16 points): $ k \leq 20 $ , and $ w_j = 1 $ for all $ j $ Subtask 6 (13 points): $ m \leq 1,000 $ Subtask 7 (22 points): $ w_j = 1 $ for all $ j $ Subtask 8 (17 points): no additional constraints

输入输出样例

输入样例 #1

6 4 10
1
2
1
4
4
3 4 5
4 7 2
5 4 1
6 9 3

输出样例 #1

9

说明

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.)