U428733 皮皮摘桃子

皮皮是一只很爱爬树的猴子，他最喜欢爬桃子树。

皮皮家的桃子树被修剪成了一棵二叉树，$1$ 号点是桃子树的根结点，其中第 $i$ 个结点结了 $a_i$ 个桃子。 皮皮爬桃子树时，只会选一条树上路径，从树上任意一个结点出发（皮皮有梯子），沿着树上路径前进，最后在树上任意一个结点停下来，然后把经过的所有结点的桃子都摘下来（每个点最多经过一次）。皮皮想知道，他一次最多能摘下多少个桃子。

第一行一个整数 $n$，表示桃子树的结点个数。 第 $2$ 到 $n+1$ 行，第 $i+1$ 行三个整数，$a_i,l_i,r_i$，表示结点 $i$ 的桃子数量，结点 $i$ 的左儿子，结点 $i$ 的右儿子，如果没有对应结点则为 $0$。

输出一行一个整数，表示皮皮一次最多能摘多少桃子。

对于 $30\%$ 的数据，$1\le n\le100$。 对于 $50\%$ 的数据，$1\le n\le 5000$。 对于 $100\%$ 的数据，$1\le n\le 10^5,1\le a_i\le 10^9$。