← 返回题目列表

Codeforces · 739/B

B. 阿廖娜和一棵树

中文机器翻译题面 查看原题

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