Get Minimum Servers

Servers form a tree rooted at 1, and edge weights may be negative. A non-root server v is unsafe if the path weight sum from v to some strict ancestor is greater than threshold[v]. Each operation deletes exactly one non-root leaf; find the minimum number of servers to delete so that all remaining nodes are safe. The root has no strict ancestor and cannot be deleted.

输入格式

The input is n, n threshold values, then n−1 lines u v weight. The complete original bounds are kept: 3≤n≤200000, nodes 1..n, and both edge weights and threshold in −10^9..10^9. The input is guaranteed to be a tree. The second example in the source contains a cycle, missing edge weights, and an isolated node, so it is not used as an example.

输出格式

Output a single integer, the answer.

样例 1

输入：

5
0 -10 5 -5 5
1 2 -2
1 3 5
3 4 -5
3 5 -3

输出：

2

样例 2

输入：

3
-1 -1 -1
1 2 -5
2 3 -5

输出：

0

样例 3

输入：

3
0 0 0
1 2 2
2 3 -10

输出：

2

样例说明

The outputs of the three public examples are, in order: 2; 0; 2. Verified by independent enumeration or direct simulation.