913B.md (1788B)
1 Source: https://codeforces.com/problemset/problem/913/B 2 3 B. Christmas Spruce 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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. 24 25 The definition of a rooted tree can be found [here](https://goo.gl/1dqvzz). 26 27 Input 28 29 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*). 30 31 Vertex 1 is the root. It's guaranteed that the root has at least 2 children. 32 33 Output 34 35 Print "Yes" if the tree is a spruce and "No" otherwise. 36 37 Examples 38 39 Input 40 41 ``` 42 4 43 1 44 1 45 1 46 ``` 47 48 Output 49 50 ``` 51 Yes 52 ``` 53 54 Input 55 56 ``` 57 7 58 1 59 1 60 1 61 2 62 2 63 2 64 ``` 65 66 Output 67 68 ``` 69 No 70 ``` 71 72 Input 73 74 ``` 75 8 76 1 77 1 78 1 79 1 80 3 81 3 82 3 83 ``` 84 85 Output 86 87 ``` 88 Yes 89 ``` 90 91 Note 92 93 The first example: 94 95  96 97 The second example: 98 99  100 101 It is not a spruce, because the non-leaf vertex 1 has only 2 leaf children. 102 103 The third example: 104 105 