二叉树

题号：NC15844
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld

题目描述

在二进制世界里, 有很多的树, 比如常见的二叉树
而二叉搜索树是比较特殊的一种二叉树, 对于树上的每个节点
它的权值大于等于它的左子树节点, 小于等于它右子树的节点

现在给你若干个二叉树, 请判断它们是否是二叉搜索树

下面是对二叉树的定义:

二叉树是递归定义的, 逻辑上二叉树有五种基本形态：

1.空二叉树——如图(a);

2.只有一个根结点的二叉树——如图(b);
3.只有左子树——如图(c);

4.只有右子树——如图(d);

5.既有左子树又有右子树——如图(e);
同样的, 左子树和右子树也是一颗二叉树

下面是对二叉搜索树的定义:

1.若任意节点的左子树不空, 则左子树上所有结点的值均小于等于它的根结点的值;

2.若任意节点的右子树不空, 则右子树上所有结点的值均大于等于它的根结点的值;

3.任意节点的左、右子树也分别为二叉查找树

输入描述:

第一行包含一个正整数T, 表示二叉树的个数
接下来有T组数据, 每组数据代表一棵二叉树信息, 格式如下:
每组数据第一行包含两个正整数m和r, 表示树上的节点数量和根节点的标号
接下来的m行按1~m标号, 第i行包含标号为i的节点的信息: 
包含三个非负整数v, a, b分别代表该节点的权值, 左儿子的节点标号和右儿子的节点标号(如果某儿子标号为0, 表示不存在该儿子)
保证每组数据给的是一棵二叉树

输出描述:

对于每组测试数据:
如果它是一颗二叉搜索树, 输出“yes”(不包括引号)
否则输出"no"(不包括引号)

示例1

输入

复制

输出

复制

yes
yes
no

备注:

1≤T≤20且为整数
0<m, r≤80000且为整数
0≤a, b≤80000且为整数