Alyona 有一个有 n 个顶点的树。树的根是顶点 1。在每个顶点中,Alyona 写了一个正整数,在顶点 i 中写了 ai。此外,女孩在树的每条边上写了一个正整数(可能在不同的边上写了不同的整数)。
让我们将 dist(v, u) 定义为写在从 v 到 u 的简单路径边缘上的整数之和。
当且仅当 u 在 v 的子树中并且 dist(v, u) ≤ au 时,顶点 v 控制顶点 u (v ≠ u)。
Alyona 想定居在某个顶点。为了做到这一点,她想知道每个顶点 v 有多少个顶点 u 使得 v 控制 u。
输入
第一行包含单个整数 n (1 ≤ n ≤ 2·105)。
第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) - 写入顶点的整数。
接下来的 (n - 1) 行每行包含两个整数。这些行中的第 i 行包含整数 pi 和 wi (1 ≤ pi ≤ n, 1 ≤ wi ≤ 109) - 树中第 (i + 1) 个顶点的父顶点以及写在 pi 和 (i + 1) 之间的边上的数字。
保证给定的图是一棵树。
输出
打印 n 个整数 — 这些数字中的第 i 个应该等于第 i 个顶点控制的顶点数。
示例
输入 #1
5 2 5 1 4 6 1 7 1 1 3 5 3 6
输出 #1
1 0 1 0 0
输入 #2
5 9 7 8 6 5 1 1 2 1 3 1 4 1
输出 #2
4 3 2 1 0
注意
在示例测试用例中,顶点 1 控制顶点 3,顶点 3 控制顶点 5(请注意,这并不意味着顶点 1 控制顶点 5)。