B. Алёна и дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алёны есть дерево из n вершин. Корень дерева — вершина с номером 1. В вершину с номером i Алёна записала положительное целое число ai. Также, девочка записала на каждом ребре дерева какое-то положительное целое число (возможно, различные числа на различных ребрах).

Определим dist(v, u) как сумму чисел, записанных на ребрах, которые лежат на кратчайшем пути из v в u.

Вершина дерева v контролирует вершину u (v ≠ u), если u лежит в поддереве v и dist(v, u) ≤ au.

Девочка хочет поселиться в некоторой вершине дерева. Для этого она хотела бы знать для каждой вершины v, сколько в дереве есть вершин u таких, что вершина v контролирует вершину u.

Входные данные

В первой строке находится одно число n (1 ≤ n ≤ 2·105).

Во второй строке находится n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — числа, записанные в вершинах.

В следующих (n - 1)-й строке находятся по 2 числа. В i-й из этих строк находятся целые числа pi и wi (1 ≤ pi ≤ n, 1 ≤ wi ≤ 109) — предок вершины (i + 1) и число, написанное на ребре от pi к (i + 1).

Гарантируется, что заданный граф — дерево.

Выходные данные

Выведите в одной строке n чисел — i-е из этих чисел должно равняться количеству вершин, которое контролируется вершиной с номером i.

Примеры
Входные данные
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
Примечание

В тесте из условия вершина 1 контролирует вершину 3, также вершина 3 контролирует вершину 5 (обратите внимание, отсюда не следует, что вершина 1 контролирует вершину 5).