CF739B Alyona and a tree

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