[树的度数] Christmas Spruce

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 p_i (1 ≤ i ≤ n - 1) — the index of the parent of the i + 1-th vertex (1 ≤ p_i ≤ 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

Output

Yes

Input

Output

No

Input

Output

Yes

Note

The first example:

The second example:

It is not a spruce, because the non-leaf vertex 1 has only 2 leaf children.

The third example:

题意:问一棵树的所有非叶子结点是否至少有三个叶子
思路:BFS搜索每个非叶子结点的叶子结点的个数,碰到少于3的输出No,否则若都大于等于3个就输出Yes

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<queue>

 using namespace std;

 typedef long long ll;

 const int amn=1e5+;

 int n,ans=,m[amn],deep[amn],idx[amn],cnt;

 vector<int> eg[amn];

 queue<int> q;

 int bfs(int rt){

     while(q.size())q.pop();q.push(rt);

     memset(deep,,sizeof deep);

     memset(idx,,sizeof idx);

     deep[rt]=;

     cnt=;

     while(q.size()){

         int u=q.front();q.pop();

         idx[u]=;

         cnt=;

         for(int i=;i<eg[u].size();i++){

             int v=eg[u][i];

             if(idx[v]||v==u)continue;

             if(!eg[v].size())cnt++; ///统计叶子结点个数

         }

         if(cnt>=){

                 for(int i=;i<eg[u].size();i++){

                 int v=eg[u][i];

                 if(idx[v]||v==u)continue;

                 if(eg[v].size())q.push(v);

             }

         }

         else return ;

     }

     return ;

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d",&m[i]);

         eg[m[i]].push_back(i);

     }

     ans=bfs();

     if(ans)

     printf("Yes\n");

     else printf("No\n");

 }

 /**

 题意:问一棵树的所有非叶子结点是否至少有三个叶子

 思路:BFS搜索每个非叶子结点的叶子结点的个数,碰到少于3的输出No,否则若都大于等于3个就输出Yes

 **/

巴特西

[树的度数] Christmas Spruce

最新文章

热门文章