当前没有测试数据。

最大BST子树

题目描述

给定一个二叉树，找到其中最大的二叉搜索树(BST)子树，并返回该子树的大小

其中：最大指的是子树节点树最多的
二叉搜索树(BST)中的节点都具备以下属性 :
左子树的值小于其父(根)节点的值
右子树的值大于其父(根节点的值)

输入格式

输入的第一行包含一个整数 $n$，表示树的结点个数。

接下来有 n 个数字，代表树的节点的值

接下来 $n-1$ 行，每行包含两个整数 $u, v$，表示结点 $u$ 和结点 $v$ 之间存在一条无向边。保证输入的数据构成一棵树。

输出格式

输出一行，包含 $1$ 个整数。表示最大的 BST 子树的大小

输入输出样例 #1

输入 #1

5
1 2
1 3
2 4
2 5

输出 #1

1

输入输出样例 #2

输入 #2

6
1 2
2 3
3 4
4 5
5 6

输出 #2

6 5 4 3 2 1

数据范围

• 对于 $100\%$ 的数据，满足 $1 \le n \le 500,000$。保证输入的各条边能组成一棵含有 $n$ 个结点的树。