第 4 题 Transport (transport)

时间限制 1.0 s · 空间限制 256 MB · 20 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 transport.in，输出文件 transport.out。

题目描述

一个国家有 $n$ 个城市，每个城市中都有一个加油站，燃料储量为 $a_i$。 有 $n - 1$ 条路径，将这些城市连接成一个树形结构。

一个货车能从城市 $u$ 到达城市 $v$，货车的燃料量必须不小于 $u, v$ 之间的距离。 每当货车抵达一个城市，就可以补充不超过加油站储量的燃料。

假设货车的油箱是无限大的，每行驶一公里需要消耗一单位燃料，请你算出有多少个有序数对 $(u, v)$ 满足：

一个油箱燃料量初始为 0 的货车，可以从城市 $u$ 出发，抵达城市 $v$，且 $u \neq v$。

请注意，货车只能走简单路径，也就是说不能走回头路。

输入格式

第一行一个正整数 $n$。 第二行有 $n$ 个正整数 $a_i$，表示每个加油站的燃料储量。 接下来 $n - 1$ 行，每行三个正整数 $u, v, w$，表示城市 $u, v$ 之间有一条长为 $w$ 的路径。

输出格式

一行一个整数表示答案。

样例

样例 1

输入：

2
3 1
1 2 2

输出：

1

样例 2

输入：

5
3 1 2 4 5
1 2 3
3 2 2
4 2 6
5 4 3

输出：

5

提示

样例 1 解释：

唯一可行的是 $(1, 2)$，即只有 $1 \to 2$ 是可行的。

数据范围：

对于 20% 的数据： $1 \le n \le 5000$ 对于 40% 的数据： 树是一条链 对于 100% 的数据： $1 \le n \le 10^5$ $1 \le u, v \le n$ $1 \le w, a_i \le 10^9$