codeforces-scrape

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

682C.md (2148B)


      1 Source: https://codeforces.com/problemset/problem/682/C
      2 
      3 C. Alyona and the Tree
      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 Alyona decided to go on a diet and went to the forest to get some apples. There she unexpectedly found a magic rooted tree with root in the vertex 1, every vertex and every edge of which has a number written on.
     22 
     23 The girl noticed that some of the tree's vertices are sad, so she decided to play with them. Let's call vertex *v* sad if there is a vertex *u* in subtree of vertex *v* such that *dist*(*v*, *u*) > *a**u*, where *a**u* is the number written on vertex *u*, *dist*(*v*, *u*) is the sum of the numbers written on the edges on the path from *v* to *u*.
     24 
     25 Leaves of a tree are vertices connected to a single vertex by a single edge, but the root of a tree is a leaf if and only if the tree consists of a single vertex — root.
     26 
     27 Thus Alyona decided to remove some of tree leaves until there will be no any sad vertex left in the tree. What is the minimum number of leaves Alyona needs to remove?
     28 
     29 Input
     30 
     31 In the first line of the input integer *n* (1 ≤ *n* ≤ 105) is given — the number of vertices in the tree.
     32 
     33 In the second line the sequence of *n* integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109) is given, where *a**i* is the number written on vertex *i*.
     34 
     35 The next *n* - 1 lines describe tree edges: *i**th* of them consists of two integers *p**i* and *c**i* (1 ≤ *p**i* ≤ *n*,  - 109 ≤ *c**i* ≤ 109), meaning that there is an edge connecting vertices *i* + 1 and *p**i* with number *c**i* written on it.
     36 
     37 Output
     38 
     39 Print the only integer — the minimum number of leaves Alyona needs to remove such that there will be no any sad vertex left in the tree.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 9  
     47 88 22 83 14 95 91 98 53 11  
     48 3 24  
     49 7 -8  
     50 1 67  
     51 1 64  
     52 9 65  
     53 5 12  
     54 6 -80  
     55 3 8
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 5
     62 ```
     63 
     64 Note
     65 
     66 The following image represents possible process of removing leaves from the tree:
     67 
     68  ![](https://espresso.codeforces.com/fbd4615a8a78d87ad6306dedff36765ece0f2f17.png)