10412: DP56 打家劫舍 III
[Creator : ]
Description
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回在不触动警报的情况下 ，小偷能够盗取的最高金额 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回在不触动警报的情况下 ，小偷能够盗取的最高金额 。
Input
第一行一个整数 $n\ (1 \leq n \leq 5\times 10^5)$。
其后 $n$ 行，第 $i$ 行包括三个整数 $lson, rson\ (1 \leq lson,rson \leq n), val\ (0 \leq val \leq 10^4)$。其中 lson,rson 分别表示编号为 $i$ 的节点的左儿子和右儿子编号，如果儿子不存在，则为 $-1$。
保证输入合法，一定能构成一棵树。
其后 $n$ 行，第 $i$ 行包括三个整数 $lson, rson\ (1 \leq lson,rson \leq n), val\ (0 \leq val \leq 10^4)$。其中 lson,rson 分别表示编号为 $i$ 的节点的左儿子和右儿子编号，如果儿子不存在，则为 $-1$。
保证输入合法，一定能构成一棵树。
Output
一行一个整数。表示答案
Sample 1 Input
5
2 3 3
-1 4 2
-1 5 3
-1 -1 3
-1 -1 1
Sample 1 Output
7
小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
Sample 2 Input
6
2 3 3
4 5 4
-1 6 5
-1 -1 1
-1 -1 3
-1 -1 1
Sample 2 Output
9
小偷一晚能够盗取的最高金额 4 + 5 = 9
Sample 3 Input
1
-1 -1 5
Sample 3 Output
5