Alyona and the Tree

### 题目描述 给你一棵树，边与节点都有权值，根节点为1，现不停删除叶子节点形成新树，问最少删掉几个点，能使得最后剩下的树内，$\forall v$与其子树内$\forall u$间边权的和小于等于点$u$权值 ### 输入输出格式 #### 输入格式： 第一行，节点个数$n(1 \leq n \leq 10^5)$ 第二行，$n$个整数——各节点的权值$a_i(1\leq a_i \leq 10^9)$ 接下来的$n-1$行，每行两个整数$p_i$与$c_i(1 \leq p_i \leq n,-10^9 \leq c_i \leq 10^9)$，分别表示编号为$i+1$的节点的父节点以及该边的边权 #### 输出格式： 一个整数，最少需要删除的点的个数

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. 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 $ . 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. 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?

In the first line of the input integer $ n $ ( $ 1<=n<=10^{5} $ ) is given — the number of vertices in the tree. In the second line the sequence of $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ) is given, where $ a_{i} $ is the number written on vertex $ i $ . 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 $ , $ -10^{9}<=c_{i}<=10^{9}) $ , meaning that there is an edge connecting vertices $ i+1 $ and $ p_{i} $ with number $ c_{i} $ written on it.

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.

9
88 22 83 14 95 91 98 53 11
3 24
7 -8
1 67
1 64
9 65
5 12
6 -80
3 8

5

The following image represents possible process of removing leaves from the tree: