题目描述

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.

题目大意

题目描述：

Alyona有一棵有 $n$ 个节点的树。这棵树的根节点是 $1$。在每个节点里，Alyona写了一个正整数，在节点 $i$ 她写了正整数 $a_i$ 。另外，她在这棵树上的每条边上写了一个正整数（不同边上可能有不同的数）。

让我们定义 $dist(v,u)$ 作为从 $v$ 到 $u$ 的简单路径上的边权和。

当且仅当 $u$ 在 $v$ 的子树中并且 $dist(v,u)\leq a_u$，顶点 $v$ 控制顶点 $u(v\neq u)$ 。

Alyona想在某些顶点定居。为了做到这件事，她想知道在每个节点 $v$ 能控制几个节点。

输入格式：

第一行包含一个整数 $n (1\leq n\leq 2\times 10^5)$

第二行有 $n$ 个整数 $a_1,a_2,\ldots,a_n(1\leq a_i\leq 10^9)$ ,作为节点 $i$ 的数。

下面的 $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)$ 的边上的数字。

数据保证是个树。

输出格式：

输出 $n$ 个整数，第 $i$ 个数为节点 $i$ 能控制的点数。

样例说明：

在样例中，节点 $1$ 控制了节点 $3$ ，节点 $3$ 控制节点 $5$ （注意，这并不代表节点 $1$ 控制了节点 $5$ ）

Translated by @lolte

5
2 5 1 4 6
1 7
1 1
3 5
3 6

1 0 1 0 0

5
9 7 8 6 5
1 1
2 1
3 1
4 1

4 3 2 1 0

提示

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