| Codeforces Round 358 (Div. 2) |
|---|
| Закончено |
Алёна решила сесть на диету и пошла в лес за яблоками. Внезапно она обнаружила волшебное корневое дерево с корнем в вершине 1, на каждом ребре и в каждой вершине которого записаны некоторые числа.
Девочка заметила, что некоторые вершины дерева грустят, поэтому она решила с ними поиграть. Назовем вершину v грустной, если в ее поддереве найдется вершина u, такая что dist(v, u) > au, где au — число, записанное в вершине u, а dist(v, u) — сумма чисел на ребрах на пути от v до u.
Листьями дерева называются вершины, соединенные ребром ровно с одной вершиной, а корень дерева является листом тогда и только тогда, когда дерево состоит из единственной вершины-корня.
Алёна решила удалять листья дерева до тех пор, пока все вершины не перестанут грустить. Какое минимальное количество листьев нужно удалить Алёне?
В первой строке входных данных записано целое число n (1 ≤ n ≤ 105) — количество вершин в дереве.
Во второй строке входных данных заданы n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109), где ai — число, записанное в вершине i.
В следующих n - 1 строках описываются ребра дерева: в i-й из этих строк записана пара чисел pi и ci (1 ≤ pi ≤ n, - 109 ≤ ci ≤ 109), означающих, что вершины i + 1 и pi дерева соединены ребром, на котором записано число ci.
Выведите минимальное количество листьев, которое требуется удалить Алёне, чтобы не осталось ни одной грустной вершины.
9
88 22 83 14 95 91 98 53 11
3 24
7 -8
1 67
1 64
9 65
5 12
6 -80
3 8
5
Процесс удаления листьев дерева из первого примера может выглядеть так:
