题目大意

在一个冒险类游戏中，参与者可以在一个由多个方格构成的地图上寻找食物。每个方格有一个编号、一个父方格编号和对应的食物单位数。参与者可以通过传送门从一个方格移动到另一个方格。 参与者可以选择任意方格作为起点，并可以在任何方格选择退出游戏。任务是计算参与者在退出时能够获得的最多食物单位数

思路

简单树上dp

1.数据结构设计：

题目内容

小红设计的这个游戏是一个冒险类游戏，参与者需要在地图上寻找食物并获得尽可能多的食物，同时需要注意在游戏过程中所处的位置，因为不同的位置可以通过传送门到达其他位置，可能会影响食物获取的数量。

在游戏开始时，参与者会出发点选择一个方格作为起点，每个方格上至多 $2$ 个传送门，通过传送门可将参与者传送至指定的其它方格。每个方格上都标注了三个数字：id 、 parent-id 和 value 。其中， id 代表方格的编号， parent-id 代表可以通过传送门到达该方格的方格编号， value 代表在该方格获取或失去的食物单位数。

参与者需要在地图上行进，到达每个方格并获取或失去对应的食物单位数，直到满足退出游戏的条件之一。参与者的最终得分是所获取食物单位数的总和，需要尽可能地高。

需要注意的是地图设计时保证了参与者不可能到达相同的方格两次。因此，参与者当前所处的方格无传送门，游戏将立即结束。另外，参与者在任意方格上都可以宣布退出游戏，同样会结束游戏。

请计算参与者退出游戏后，最多可以获得多少单位的食物。

输入描述

第一行：方块个数 $N$ ( $N\le 10000$ )

接下来 $N$ 行，每行三个整数 id ， parent-id ， value ，具体含义见题面。

$0\le id,parent-id \lt N$ ， $-100\le value \le 100$

特殊的 parent-id 可以取 $-1$ 则表示没有任何方格可以通过传送门传送到此方格，这样的方格在地图中有且仅有一个。

输出描述

输出为一个整数，表示参与者退出游戏后最多可以获得多少单位的食物。

样例

样例1

输入

7
0 1 8
1 -1 -2
2 1 9
4 0 -2
5 4 3
3 0 -3
6 2 -3

输出

9

样例解释

参与者从方格 $0$ 出发，通过传送门到达方格 $4$ ，再通过传送门到达方格 $5$ 。一共获得 $8+(-2) +3=9$ 个单位食物，得到食物最多或者参与者在游戏开始时处于方格 $2$ ，直接主动宣布退出游戏，也可以获得 $9$ 个单位食物。

样例2

输入

3
0 -1 3
1 0 1
2 0 2

输出

5

样例解释

参与者从方格 $0$ 出发，通过传送门到达方格 $2$ ，一共可以获得 $3+2=5$ 个单位食物，此时得到食物最多。