陈远龙精品编程（信奥赛） 助力信奥赛学子取得优秀的成绩

题目描述

二叉树的路径是指从二叉树的根节点到叶子节点的一条路径，显然一颗二叉树可以有多条不同的路径，比如：

这个二叉树有以下几条路径：

10 -> 5 -> 3

10 -> 5 -> 401

10 -> 20

路径和指的是二叉树的一条路径中所有的节点的值相加之后的结果，比如：

10 -> 5 -> 3的路径和为：10 + 5 + 3 => 18

现在给出特定格式的二叉树数据，请你编写程序找出这棵二叉树中所有路径和中的最大路径和

比如上面的二叉树中，二叉树最大路径和是：416（10 -> 5 -> 401这条路径：10 + 5 + 401）

输入格式

第1行，一个正整数N，代表接下来会有N个二叉树的节点信息

接下来的N行，每行描述一个二叉树节点信息，有三个正整数，分别用C、L、R表示，用空格分隔

C L R

其中C代表当前节点里的值，L代表当前节点左子树根节点的值，R代表当前节点右子树节点根节点的值

比如上图中的二叉树的描述信息是：

10 5 20
5 3 401
20 0 0
3 0 0
401 0 0

其中用L、R为0的时候代表的是空节点

这里约定，输入的第1行C L R数据是二叉树的根节点信息，从第2行开始不保证某种特定的顺序的输入节点数据哦

注意每个二叉树节点中的值都是互不相同的正整数

输入的数据保证二叉树根节点有非空的左子树和非空的右子树

输出格式

1行，1个整数，代表这棵二叉树中最大的路径和

输入输出样例

输入样例	输出样例
5 10 5 20 5 3 401 20 0 0 3 0 0 401 0 0	416

数据范围与提示

100%的数据：$3 \le N \le 10$，$1 \le C, L, R \le 1000$，保证二叉树根节点有非空的左子树和非空的右子树

测试点数目

共10个测试点，每个测试点10分

时间与内存限制

每个测试点时间：1000ms（1.0s），内存：256MiB

输入输出模式

本OJ支持两种输入输出模式