题目背景

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

题目描述

一个地下掩体由 $n$ 个房间组成，这些房间通过 $n - 1$ 条走廊相连。每条走廊连接两间不同的房间，并具有一定的长度。掩体的结构保证了从任意一个房间 $i$ 都可以到达另一个房间 $j$。注意，存在且仅存在一条路径，使得在该路径中没有任何走廊被重复经过。由这些走廊长度的总和定义为房间 $i$ 与房间 $j$ 之间的距离，记作 $\rho(i, j)$。

每个房间都装有一套声响警报系统，由警报器（喇叭）和声波感应器组成。当房间 $i$ 的警报器被启动时，它会激活所有与其距离不超过 $d_i$ 的房间的声波感应器，其中 $d_i$ 表示该警报器的有效传播半径。换句话说，如果房间 $i$ 的警报器被启动，那么所有满足 $\rho(i, j) \le d_i$ 的房间 $j$ 的警报器也会被自动启动。这些被自动启动的警报器反过来又可能触发更多的警报器，以此类推。

在紧急情况下，需要人工启动一部分警报器。这些被人工启动的警报器会自动触发其他警报器，最终应当使得所有房间的警报器都被启动。安全规范要求必须选择一个最小的人工启动警报器集合，以确保最终所有房间的警报器都会被启动。

请编写一个程序，计算满足安全规范所需的最少人工启动警报器数量。

输入格式

第一行包含一个整数 $n$ —— 房间的数量。

第二行包含 $n$ 个整数 $d_i$，第 $i$ 个整数表示位于第 $i$ 间房间的警报器的最大传播距离（$0 \le d_i \le 10^9$）。

接下来的 $n - 1$ 行描述了掩体内的走廊。第 $i$ 行包含三个整数 $u_i$, $v_i$, $l_i$，其中 $u_i$ 和 $v_i$ 是被走廊连接的两个不同房间编号，$l_i$ 表示该走廊的长度（$1 \le u_i, v_i \le n$；$1 \le l_i \le 10^9$）。

输出格式

输出一个整数 —— 表示必须人工启动的警报器的最小数量。

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 的警报器。

:::align{center} :::

数据范围

子任务编号	分值	$n$ 的范围
1	16	$1 \le n \le 15$
2	23	$1 \le n \le 100$
3	17	$1 \le n \le 3000$
4	24	$1 \le n \le 100\,000$
5	20	$1 \le n \le 300\,000$