4053: 二叉搜索树
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：21
解决：9
题目描述
给定一棵包含 n 个结点的有根二叉树，结点依次以 1~n 编号，根结点编号为 1。
对于结点 u，其左儿子编号记为 l，右儿子编号记为 r。如果左儿子不存在则 l=0，右儿子不存在则 r=0。
请求出所有 n 棵子树中，有多少棵子树是二叉搜索树。
二叉搜索树是指：对于树中任意结点，其左子树中所有结点的编号都小于该结点编号，其右子树中所有结点的编号都大于该结点编号。
输入
第一行，一个正整数 n
接下来 n 行，每行两个非负整数 l[i] 和 r[i]
输出
一行一个整数，二叉搜索树子树的数量。
样例输入 复制
3
2 0
3 0
0 0样例输出 复制
1提示
50% 测试点：n ≤ 1000
100% 测试点：n ≤ 100,000
100% 测试点：n ≤ 100,000