codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![](https://espresso.codeforces.com/a028cc3eb93ff24e14e12c093bc7fd0e0d9f7a1a.png)
     96 
     97 The second example:
     98 
     99 ![](https://espresso.codeforces.com/e6c7b518972d13e2572004d8ce21cda77de4c938.png)
    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 ![](https://espresso.codeforces.com/9af8f35bd8ce5823176fec24fc464c670bf95c3e.png)