913B

Problem:

B. Christmas Spruce
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Consider a rooted tree. A rooted tree has one special vertex called the root. All edges are directed from the root. Vertex u is called a child of vertex v and vertex v is called a parent of vertex u if there exists a directed edge from v to u. A vertex is called a leaf if it doesn’t have children and has a parent.

Let’s call a rooted tree a spruce if its every non-leaf vertex has at least 3 leaf children. You are given a rooted tree, check whether it’s a spruce.

The definition of a rooted tree can be found here.

Input

The first line contains one integer n — the number of vertices in the tree (3 ≤ n ≤ 1 000). Each of the next n - 1 lines contains one integer pi (1 ≤ i ≤ n - 1) — the index of the parent of the i + 1-th vertex (1 ≤ pi ≤ i).

Vertex 1 is the root. It’s guaranteed that the root has at least 2 children.

Output

Print “Yes” if the tree is a spruce and “No” otherwise.

Examples
input
4
1
1
1
output
Yes
input
7
1
1
1
2
2
2
output
No
input
8
1
1
1
1
3
3
3
output
Yes

Solution:

Notes:

void * memset ( void * ptr, int value, size_t num )

Although the second parameter is entered as int value, it will be converted to unsigned char of this int when filling in these memory spaces. Have to use loops to fill an array with numbers other than zero.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s