题目描述

给你一棵以 root= 1 为根的  二叉树  ，请你返回 任意  二叉搜索子树的最大键值和。

二叉搜索树的定义如下：

• 任意节点的左子树中的键值都  小于  此节点的键值。
• 任意节点的右子树中的键值都 大于  此节点的键值。
• 任意节点的左子树和右子树都是二叉搜索树。

输入格式

第一行空格分开的两个整数，第一个整数 $n$ 表示此树共有的结点数，第二个整数表示根节点的键值；

接下来 $n - 1$ 行，每行两个空格隔开的整数，第一个表示编号 $i+1$ 的父亲编号， 第二个表示此节点的键值；第一次出现的为左孩子。

输出格式

一行一个整数表示答案。

示例 1：

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

20

解释: 键值为 3 的子树是和最大的二叉搜索树。

示例 2：

4 4
1 3
2 1
2 2

2

解释: 键值为 2 的单节点子树是和最大的二叉搜索树。

示例 3：

3 -4
1 -2
1 -5

0

解释: 所有节点键值都为负数，和最大的二叉搜索树为空。

示例 4：

3 2
1 1
1 3

6

示例 5：

6 5
1 4
1 8
2 3
3 6
3 3

7

提示：

• 每棵树有 1 到 40000 个节点。
• 每个节点的键值在 [-4 * 10^5 , 4 * 10^5] 之间。

SOURCE

二叉搜索子树的最大键值和