4515: 【基础】是否是完全二叉树(2187)

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

题目描述

棵深度为 lns="http://www.w3.org/1998/Math/MathML">k 的有 lns="http://www.w3.org/1998/Math/MathML">n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 lns="http://www.w3.org/1998/Math/MathML">i（lns="http://www.w3.org/1998/Math/MathML">1≤i≤n）的结点与满二叉树中编号为 lns="http://www.w3.org/1998/Math/MathML">i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。

现在根据边的连接情况判断一棵树是否是完全二叉树。

输入

第一行有 lns="http://www.w3.org/1998/Math/MathML">2 个整数 lns="http://www.w3.org/1998/Math/MathML">n (lns="http://www.w3.org/1998/Math/MathML">0<n<1024)和 lns="http://www.w3.org/1998/Math/MathML">r (lns="http://www.w3.org/1998/Math/MathML">1≤r≤n), 表示结点数和树根。

接下来 lns="http://www.w3.org/1998/Math/MathML">n−1 行每行有 lns="http://www.w3.org/1998/Math/MathML">2 个整数 lns="http://www.w3.org/1998/Math/MathML">a,b (lns="http://www.w3.org/1998/Math/MathML">1≤a,b≤n)表示 lns="http://www.w3.org/1998/Math/MathML">a 结点和 lns="http://www.w3.org/1998/Math/MathML">b 结点有一条边相连，如果 lns="http://www.w3.org/1998/Math/MathML">a 是 lns="http://www.w3.org/1998/Math/MathML">b 的根结点，则 lns="http://www.w3.org/1998/Math/MathML">b 是 lns="http://www.w3.org/1998/Math/MathML">a 的左子结点，如果 lns="http://www.w3.org/1998/Math/MathML">b 是 lns="http://www.w3.org/1998/Math/MathML">a 的根结点，则 lns="http://www.w3.org/1998/Math/MathML">a 是 lns="http://www.w3.org/1998/Math/MathML">b 的右子结点（数据保证是一棵树而不是一座森林)

输出

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

样例输入 复制 

5 1
1 2
3 1
4 2
2 5

样例输出 复制 

yes

来源/分类

提交提交记录统计露一手!