问题 D: 判断完全二叉树[need data]

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:11 解决:9

题目描述

一棵深度为 k 的有 n 个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为 i(1≤i≤n)的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。

完全二叉树的特点:叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。
现在根据边的连接情况判断一棵树是否是完全二叉树。

输入

第一行有 2 个整数 n (0<n<1024)和 rr (1≤r≤n), 表示结点数和树根。
接下来 n−1 行每行有 2 个整数 a,b (1≤a,b≤n)表示 a 结点和 b 结点有一条边相连,如果 a 是 b 的根结点,则 b 是 a 的左子结点,如果 b 是 a 的根结点,则 a 是 b 的右子结点(数据保证是一棵树而不是一座森林)

输出

如果是完全二叉树,输出 yes ,否则输出 no。

样例输入 复制

5 1
1 2
3 1
4 2
2 5 

样例输出 复制

yes