题目描述

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

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

假设货车的油箱是无限大的，请你算出有多少个有序数对 $(u,v)$ 满足：
一个油箱燃料量初始为 $0$ 的货车，可以从城市 $u$ 出发，抵达城市 $v$。

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

输入格式

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

输出格式

一行一个整数表示答案。

2
3 1
1 2 2

1

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

5

提示

样例1解释：

唯一可行的是 $(1,2)$，即只有 $1\rightarrow 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$