题目描述

译自 COCI 2018/2019 Contest #5 T5「Transport」

某个遥远的国度一共有 $N$ 个城市，这些城市由恰好 $N-1$ 条路径连接，使得所有城市相互连通。每个城市都有且仅有一个加油站。已知每条路径的长度和每个加油站具有的燃料分量。

由于不久前刚经历过能源危机，行业协会想了解目前各个城市之间公路运输的能力。假设长途货车每行驶一公里距离要消耗一单位燃料，货车能够从城市 $i$ 抵达某个相邻城市 $j$ 当且仅当货车离开城市 $i$ 时具有的燃料量大于或等于道路 $(i,j)$ 的长度。每当货车抵达一个城市，可以在加油站补充不超过加油站燃料分量的燃料。

假设货车的油箱具有无限容量。请你计算，一共有多少个有序城市对 $(A,B)$ 满足，油箱燃料最初为 $0$ 的货车可以从城市 $A$ 出发经过一些城市抵达城市 $B$（货车离开城市 $A$ 时会加满城市 $A$ 的加油站燃料数）。

输入格式

第一行，是一个正整数 $N$。

第二行，是 $N$ 个正整数 $A_i$，依次表示城市 $1\sim N$ 的加油站燃料量。

接下来 $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

数据范围与提示

对于 $100\%$ 的数据，$1\leq N\leq 10^5, 1\leq U, V\leq N, 1\leq A_i\leq 10^9, 1\leq W\leq 10^9$。