题目描述

译自 ROI 2015 Day2 T4. Сигнализация

地下掩体由 $n$ 个房间组成，通过 $n - 1$ 条走廊相连接。每条走廊连接两个不同的房间，并具有一定的长度。掩体的结构使得从任意房间 $i$ 可以到达任意其他房间 $j$。值得注意的是，存在唯一一条不重复经过同一条走廊的路径。构成该路径的走廊长度之和称为房间 $i$ 和 $j$ 之间的距离，记为 $\rho(i, j)$。

掩体的每个房间都装备有声音报警系统，包括警报器和声音传感器，传感器会触发警报器。在房间 $i$ 中启动的警报器会激活距离不超过 $d_i$ 的所有房间中的声音传感器，其中 $d_i$ 由该警报器的功率决定。换句话说，在房间 $i$ 启动警报器会自动触发所有满足 $\rho(i, j) \leq d_i$ 的房间 $j$ 中的警报器。这些警报器又可能依次触发其他警报器，依此类推。

在紧急情况下，需要手动启动某些警报器，之后它们的声音会自动触发其他房间的警报器。安全规定要求选择一组需要手动启动的警报器，使最终能自动触发所有房间中的警报器。

你的任务是编写一个程序，确定满足安全规定的最小警报器手动启动数量。

输入格式

输入数据的第一行包含一个整数 $n$，表示房间数量。

第二行包含 $n$ 个整数 $d_i$ $(0 \leq d_i \leq 10^9)$，第 $i$ 个数字表示位于房间 $i$ 的警报器能激活传感器的最大距离。

接下来的 $n - 1$ 行描述掩体的走廊。每行包含三个整数 $u_i, v_i, l_i$ $(1 \leq u_i, v_i \leq n, 1 \leq l_i \leq 10^9)$，其中 $u_i$ 和 $v_i$ 是由第 $i$ 条走廊连接的两个不同房间的编号，$l_i$ 是该走廊的长度。

输出格式

输出一行，包含一个整数，表示需要手动启动的最小警报器数量。

10
1 2 2 2 6 3 4 5 4 3
1 2 5
2 3 1
2 4 5
4 5 2
4 6 4
4 7 3
1 8 1
8 9 5
8 10 4

3

在样例中，房间 $4$ 的警报器会触发房间 $5$ 的警报器，而房间 $5$ 的警报器又会触发房间 $6$ 和 $7$ 的警报器。房间 $2$ 的警报器会触发房间 $3$ 的警报器。房间 $8$ 的警报器会触发房间 $1$、$9$ 和 $10$ 的警报器。

数据范围与提示

详细子任务附加限制及分值如下表所示：