← 返回题目列表

Codeforces · 913/B

B. 圣诞云杉

中文机器翻译题面 查看原题

考虑一棵有根的树。一棵有根树有一个特殊的顶点,称为根。所有的边都是从根开始的。如果存在从 v 到 u 的有向边,则顶点 u 称为顶点 v 的子节点,并且顶点 v 称为顶点 u 的父节点。如果一个顶点没有子节点但有父节点,则该顶点称为叶节点。

如果一棵有根树的每个非叶顶点至少有 3 个子叶,我们就将其称为云杉。给你一棵有根的树,检查它是否是云杉。

有根树的定义可以在这里找到。

输入

第一行包含一个整数 n — 树中的顶点数 (3 ≤ n ≤ 1 000)。接下来的 n - 1 行中的每一行都包含一个整数 pi (1 ≤ i ≤ n - 1) - 第 i + 1 个顶点 (1 ≤ pi ≤ i) 的父顶点的索引。

顶点 1 是根。保证 root 至少有 2 个孩子。

输出

如果树是云杉,则打印“是”,否则打印“否”。

示例

输入 #1

4
1
1
1

输出 #1

Yes

输入 #2

7
1
1
1
2
2
2

输出 #2

No

输入 #3

8
1
1
1
1
3
3
3

输出 #3

Yes

注意

第一个例子:

第二个例子:

它不是云杉,因为非叶子顶点 1 只有 2 个叶子子节点。

第三个例子: