A10758. Alyona and a tree

Alyona has a tree with $n$ vertices. The root of the tree is the vertex $1$ . In each vertex Alyona wrote an positive integer, in the vertex $i$ she wrote $a_{i}$ . Moreover, the girl wrote a positive integer to every edge of the tree (possibly, different integers on different edges).

Let's define $dist(v,u)$ as the sum of the integers written on the edges of the simple path from $v$ to $u$ .

The vertex $v$ controls the vertex $u$ ( $v≠u$ ) if and only if $u$ is in the subtree of $v$ and $dist(v,u)<=a_{u}$ .

Alyona wants to settle in some vertex. In order to do this, she wants to know for each vertex $v$ what is the number of vertices $u$ such that $v$ controls $u$ .

The first line contains single integer $n$ ( $1<=n<=2·10^{5}$ ).

The second line contains $n$ integers $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=10^{9}$ ) — the integers written in the vertices.

The next $(n-1)$ lines contain two integers each. The $i$ -th of these lines contains integers $p_{i}$ and $w_{i}$ ( $1<=p_{i}<=n$ , $1<=w_{i}<=10^{9}$ ) — the parent of the $(i+1)$ -th vertex in the tree and the number written on the edge between $p_{i}$ and $(i+1)$ .

It is guaranteed that the given graph is a tree.

Print $n$ integers — the $i$ -th of these numbers should be equal to the number of vertices that the $i$ -th vertex controls.

In the example test case the vertex $1$ controls the vertex $3$ , the vertex $3$ controls the vertex $5$ (note that is doesn't mean the vertex $1$ controls the vertex $5$ ).