CF739B.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.

Alyona 有一棵包含 $n$ 个顶点的树，树的根节点为顶点 $1$。在每个顶点上，Alyona 写了一个正整数；在顶点 $i$ 上她写的是 $a_i$。此外，该女孩还在树的每条边上写了一个正整数（不同边上的数可能不同）。

定义 $\text{dist}(v, u)$ 为从 $v$ 到 $u$ 的简单路径上所有边所写数字之和。

当且仅当 $u$ 位于 $v$ 的子树中，且 $\text{dist}(v, u) \leq a_u$ 时，顶点 $v$ 控制顶点 $u$（其中 $v \neq u$）。

Alyona 想定居在某个顶点上。为此，她希望对每个顶点 $v$，都求出满足 $v$ 控制 $u$ 的顶点 $u$ 的个数。

The first line contains single integer n (1 ≤ n ≤ 2·105).

The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) — 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 ≤ 109) — 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.

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）——表示写在各个顶点上的整数。

接下来的 $(n - 1)$ 行，每行包含两个整数。其中第 $i$ 行包含整数 $p_i$ 和 $w_i$（$1 \leq p_i \leq n$，$1 \leq w_i \leq 10^9$）——分别表示树中第 $(i + 1)$ 个顶点的父节点，以及连接 $p_i$ 与 $(i + 1)$ 的边上的数值。

保证所给图是一棵树。

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

输出 n 个整数——其中第 i 个数应等于第 i 个顶点所控制的顶点数量。

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).

在示例测试用例中，顶点 1 控制顶点 3，顶点 3 控制顶点 5（注意：这并不意味着顶点 1 控制顶点 5）。